[백준 9465][Python][DP] 스티커

문제 바로가기

9465번: 스티커

Algorithm

Dynamic Programming

 

Logic

스티커를 고르는 경우는 i번째 위치에서 위를 선택/아래를 선택/고르지 않기 세 가지 경우이다.

그 전에 위에 있는 스티커를 골랐다면, 현재 위치에서도 위의 스티커는 고를 수 없다.

그 전에 아래에 있는 스티커를 골랐다면, 현재 위치에서도 아래의 스티커는 고를 수 없다.

이렇게 불가능한 경우에 유의하면서 코드를 작성하면 된다.

 

*핵심코드

for i in range(1, n+1):
    answer[0][i] = max(answer[1][i-1] + sticker[0][i], answer[2][i-1] + sticker[0][i])
    answer[1][i] = max(answer[0][i-1] + sticker[1][i], answer[2][i-1] + sticker[1][i])
    answer[2][i] = max(answer[0][i-1], answer[1][i-1], answer[2][i-1])

answer의 0번째가 위를 선택한 것이고, 1번째가 아래를 선택한 것이고, 2번째가 고르지 않은 경우이다.

만약 위에 있는 스티커를 고른다고 하면, 그 전에 아래에 스티커를 골랐을 때의 점수와 그 전에 스티커를 고르지 않았을 때의 점수 중 큰 점수를 택하여 그 위치의 스티커 점수만큼 더해준 것이 현재 위에 있는 스티커의 점수가 될 것이다.

 

Code

T = int(input())
for t_c in range(T):
    n = int(input())
    sticker = [[int(x) for x in input().split()]for _ in range(2)]
    sticker[0].insert(0,0)
    sticker[1].insert(0,0)
    answer = [[0 for _ in range(n+1)]for _ in range(3)]

    for i in range(1, n+1):
        answer[0][i] = max(answer[1][i-1] + sticker[0][i], answer[2][i-1] + sticker[0][i])
        answer[1][i] = max(answer[0][i-1] + sticker[1][i], answer[2][i-1] + sticker[1][i])
        answer[2][i] = max(answer[0][i-1], answer[1][i-1], answer[2][i-1])

    # print(answer)
    print(max(answer[0][n], answer[1][n], answer[2][n]))