백준 9465 스티커

https://www.acmicpc.net/problem/9465

 

 이 문제는 가로로 N줄 세로로 2줄인 스티커 배열이 주어진다. 스티커 배열 안의 스티커는 각자 점수가 있다. 어떠한 스티커를 떼어낸다면 그 스티커와 변이 맞닿아있는 스티커는 못 쓴다는 설정이다. 

 이러한 경우 스티커 배열에서 가장 점수가 높게 스티커를 떼어낼 때의 점수를 출력하는 것이 문제이다.

 

 이 문제는 언뜻 보면 브루트포스처럼 모든 것을 해야할 것 처럼 보이지만, 이 문제 또한 일종의 다이나믹 프로그래밍 문제이다. 이 문제를 왼쪽부터 훑어가면서 특정 스티커를 뽑을 때, 이 스티커를 뽑을 수 있게하는 직전 스티커들 중, 가장 점수가 높은 것들을 따라가는 식으로 하면된다. 이게 말로하면 복잡한데 그림으로 그려주자면 

 내가 지금 체크표시한 스티커를 떼어내겠다 한다면, 왼쪽부터 훑어갈 것이니 오른쪽은 볼 필요 없고, 엑스자들은 떼어내지 못하는 부분이니, 빗금칠 한 스티커들 중 가장 점수가 높았던 경로에서 시작해 체크표시한 스티커를 뗀다는 감각으로 코드를 짜야한다. 그런데 실상은 저 빗금칠 중에서 가장 오른쪽의 3칸만 따지면 된다. 그 이유는 3칸 왼쪽의 스티커는 오른쪽 3칸 스티커의 경로에 이미 포함되어 있을 것이므로 3칸 중 가장 스티커 점수가 높았던 경로에서 스티커를 떼어간다. 는 감각으로 코드를 짜면 된다.

 

import sys
input = sys.stdin.readline

def find_best(N,sticker):
    matrix = [[0 for x in range(N)] for y in range(2)]
    matrix[0][0] = sticker[0][0]#미리 입력
    matrix[1][0] = sticker[1][0]

    for idx in range(1,N):
        if idx==1:#1개만 따지기
            matrix[0][idx] = matrix[1][0]+sticker[0][idx]
            matrix[1][idx] = matrix[0][0]+sticker[1][idx]
        else:#3개 따지기
            matrix[0][idx] = max([matrix[0][idx-2]]+matrix[1][idx-2:idx]) + sticker[0][idx]
            matrix[1][idx] = max([matrix[1][idx-2]]+matrix[0][idx-2:idx]) + sticker[1][idx]

    return max(matrix[0][-2:]+matrix[1][-2:])

for _ in range(int(input().rstrip())):
    N=int(input().rstrip())
    sticker = []
    for i in range(2):
        sticker.append(list(map(int,input().rstrip().split())))

    print(find_best(N,sticker))