백준: 9465 스티커

문제

9465번: 스티커

 

문제 풀이

 

 스티커를 제거 할 때 다음과 같은 규칙이 적용된다. 변을 인접하고 있으면 동시에 스티커가 제거되어 선택할 수 없으므로 대각선으로 선택하여야 한다. 스티커의 점수가 최대가 되기 위해서는 대각선의 점수를 합하여 최대 값을 찾으면 된다.

 

 첫 번째 행에서 시작하게 된다면 `↘↗↘↗` 와 같이 스티커를 선택하게 된다. 이와 반대로 두 번째 행의 경우 `↗↘↗↘` 와같이 스티커를 선택하게 된다. 첫 번째 열과 두 번째 열은단순히대각선의합을구하면되지만

단순히 대각선의 합을 구하면 되지만, 세 번째 열부터는 바로 옆의 대각선과 그다음 대각선을 비교하여 큰 값을 선택하도록 하여야 한다.

 

코드

from sys import stdin


if __name__ == '__main__':
    UP, DOWN = 0, 1
    T = int(input())
    for _ in range(T):
        n = int(stdin.readline())
        sticker = \
            [list(map(int, stdin.readline().split())) for _ in range(2)]

        # 1행을 기준으로 시작할 경우
        sticker[DOWN][1] += sticker[UP][0]
        # 2행을 기준으로 시작할 경우
        sticker[UP][1] += sticker[DOWN][0]

        for i in range(2, n):
            sticker[UP][i] += max(sticker[DOWN][i - 1], sticker[DOWN][i - 2])
            sticker[DOWN][i] += max(sticker[UP][i - 1], sticker[UP][i - 2])
        print(max(sticker[UP][n - 1], sticker[DOWN][n - 1]))