[CLASS 4]백준 9465번 - 스티커

9465번 : 스티커

 

이 문제를 풀고 확신한 것이 있다. 난 DP를 못한다. 이 문제를 푸는데 한참 걸렸다. 먼저 DP인줄 알기 전까지 다른 방법으로 뻘짓하느라 시간을 날리고, DP인것을 깨닫고 나서 부터도 구현하는데 한참 걸렸다. DP문제만 모아서 왕창 풀어봐야겠다.

 

내 코드:

from sys import stdin
input = stdin.readline
for _ in range(int(input())):
    sticker = []

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

    cache = [[sticker[0][0],sticker[1][0]+sticker[0][1]],[sticker[1][0],sticker[0][0]+sticker[1][1]]]

    for i in range(2,length):
        cache[0].append(max(cache[1][i-2],cache[1][i-1])+sticker[0][i])
        cache[1].append(max(cache[0][i-2],cache[0][i-1])+sticker[1][i])
    
    print(max(cache[0][-1],cache[1][-1]))

 

cache[n][i]는 길이 n의 스티커에서 마지막에 i (0은 위, 1은 아래) 를 골랐을 때의 최대값이다.

 

 

이렇게 n번째의 0번 row의 값을 정할 때에는 그림처럼 두가지 경우가 있다.

 

첫 번째 경우는 cache의 한칸 왼쪽 한칸 아래에 저장되어 있다.

 

두 번째 경우는 cache의 두칸 왼쪽 한칸 아래에 저장되어 있다.

 

이 두가지 중 큰 경우의 값 + 해당 칸(n)의 스티커 값을 더해서 cache[n]에 저장하면 된다.

 

그리고 이 짓을 대칭적으로 아래 줄에서도 시행하면 된다.

 

dp테이블을 이중 리스트로 해야 된다는 생각을 못하고 그냥 리스트 (cache[n]꼴)로 해보려고 악을 쓰다가 시간을 많이 날렸다.