[Baekjoon 9465 / Python / 실버1] 스티커

문제

 

DP 문제이다. 언제나 어렵고 새롭고 가장 싫어하는 알고리즘이다.

 

# 실버1 -> DP

import sys

input = sys.stdin.readline

# 테스트 케이스 개수

T = int(input())

for _ in range(T):

    N = int(input()) # 스티커 길이

    sticker = []

    sticker.append(list(map(int, input().split())))

    sticker.append(list(map(int, input().split())))

    if N == 1:

        print(max(sticker[0][0], sticker[1][0]))

        continue

    dp = [[0] * (N + 1) for _ in range(3)]

    dp[1][1] = sticker[0][0]

    dp[2][1] = sticker[1][0]

    # DP 테이블 채우기

    for i in range(2, N + 1):

        dp[0][i] = max(dp[1][i-1], dp[2][i-1])

        dp[1][i] = max(sticker[0][i-1] + dp[0][i-1], sticker[0][i-1] + dp[2][i-1])

        dp[2][i] = max(sticker[1][i-1] + dp[0][i-1], sticker[1][i-1] + dp[1][i-1])

   

    # 결과 출력

    print(max(dp[1][N], dp[2][N]))

 

스티커를 선택하면 상하좌우에 붙어있는 스티커가 함께 뜯겨 나간다. 최대한 많은 스티커를 고르는 방법은, 대각선 아래 또는 대각선 위로 윗줄과 아랫줄을 번갈아가며 고르는 것이다.

따라서 0행 0열, 1행 0열에서 시작하여 대각선을 따라 진행하면 최대한 많은 스티커와 점수를 얻을 수 있다.

 

그러나 이 방법이 모든 경우의 수를 포함하지 않는다. 왜냐하면 스티커를 고르지 않고 건너뛰어서 더 큰 점수의 스티커를 골라야 할 때도 있기 때문이다.

 

채워진 DP 테이블

 

위쪽은 테스트 케이스 입력값, 아래쪽은 테스트 케이스에 대하여 최종적으로 만들어진 DP 테이블이다.

DP 테이블의 가장 첫 번째 줄은 , 스티커 전전 값 2개 중 더 큰 값을 의미한다.

 

열을 하나 채울 때 마다, 이전 열의 대각선 값 OR 이전 열의 0행 값(전전값중 더 큰 값) 중 더 큰 값과 더해주면 된다.

이렇게 하면 대각선으로 최대한 많은 스티커를 고르되, 기댓값이 큰 스티커를 얻기 위해 건너뛰는 경우까지 모두 포함할 수 있다. DP 테이블을 채운 후 1행과 2행 마지막 열 값 중 더 큰 값을 출력해 주면 된다.

 

결과