[Python] 백준 9465번: 스티커

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

9465번: 스티커

import sys
input = sys.stdin.readline


def getMaxScore(stickers, n):
    for j in range(n):
        for i in range(2):
            if j == 0:
                continue
            elif j == 1:
                stickers[i][j] += stickers[(i+1) % 2][j-1]
            else:
                stickers[i][j] += max(
                    stickers[(i+1) % 2][j-1],
                    stickers[(i+1) % 2][j-2],
                    stickers[i][j-2]
                )
    print(stickers)
    return max(max(stickers[0]), max(stickers[1]))


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        n = int(input())
        stickers = [list(map(int, input().split())),
                    list(map(int, input().split()))]

        maxScore = getMaxScore(stickers, n)
        print(maxScore)

문제를 분석해보면, 최댓값을 구하기 위한 선택사항이 매우 적다는 것을 알 수가 있다.

가령, 50에서는, 밑줄 친 3개의 경우로 갈 수가 있다. 이 특성을 이용하여 DP를 구현하였다. 우선 DP의 결과는 다음과 같다.

1. 첫번째 열은 스티커의 값 그대로이다.

2. 두번째 열은 스티커 값에 대각선으로 왼쪽의 이전 값을 가져와서 더해준다.(가령, 2번째 줄의 점수 10의 스티커의 경우, 10 + 30 = 40)

3. 세번째 열 이후에는, 총 3가지 선택지가 있다.

이런 식으로 말이다. 저 선택지들에서 맥스값을 가져와주면 된다.

 

이렇게 dp를 수행한 후, 마지막으로 가장 큰 값을 출력해주면 된다.