문제
풀이
DP를 풀 때에는 항상 어느 한 기점에서 최대 또는 최소 값을 가질 수 있는 방법을 생각해 보는 것이 좋은 것 같다.
그림에서 한 가지의 스티커를 선택해 보자. 그리고 그 스티커를 기준으로 최댓값을 구할 수 있는 경우의 수를 생각해 보는 것이다.
저 농구 공 스티커를 기준으로 잡았다고 해 보자.
그렇다면 농구 공의 스티커의 밑, 왼쪽, 오른쪽에 있는 스티커는 선택하지 못한다.
그럼 농구 공 스티커는 선택지가 두 개가 남는다. 하나는 "자신과 자신의 대각선 밑에 있는 지금까지 쌓아온 최댓값"과 "대각선 밑을 포기하고 그 옆의 지금까지 쌓아온 최댓값의 스티커와 자기 자신" 이 두 가지를 선택하는 것이다.
여기서 굵게 표시한 것이 바로 메모제이션을 한 array이다. 이것을 코드로 적용하면 된다.
스티커는 윗줄과 아랫줄, 두 가지로 나뉘기 때문에 for문이 한 번 돌 때 마다 위의 스티커와 아래의 스티커를 둘 다 계산해 주면 된다.(마찬가지로 스티커 하나를 기준으로 잡는다.)
t = int(input())
for _ in range(t):
n = int(input())
cacheUp = [0 for _ in range(n+1)]
cacheDown = [0 for _ in range(n+1)]
stickerUp = list(map(int, input().split()))
stickerDown = list(map(int, input().split()))
stickerUp.insert(0, 0)
stickerDown.insert(0, 0)
cacheUp[1] = stickerUp[1]
cacheDown[1] = stickerDown[1]
if n == 1:
print(max(stickerDown[1], stickerUp[1]))
continue
cacheUp[2] = stickerUp[2]+stickerDown[1]
cacheDown[2] = stickerDown[2]+stickerUp[1]
for i in range(3, n+1):
cacheUp[i] = max(cacheDown[i-1]+stickerUp[i],
cacheDown[i-2]+stickerUp[i])
cacheDown[i] = max(cacheUp[i-1]+stickerDown[i],
cacheUp[i-2]+stickerDown[i])
print(max(cacheDown[n], cacheUp[n]))
댓글
댓글 쓰기