2156 포도주 시식

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(input())

graph = [0]
for i in range(1,N+1):
    graph.append(int(input()))

dp_table = [0]*(N+1)

if N == 1 :
    print(graph[1])
elif N == 2:
    print(graph[1]+graph[2])
else :
    dp_table[1] = graph[1]
    dp_table[2] = graph[1]+graph[2]
    for j in range(3,N+1):
        # print(j,dp_table[j-2],graph[j-1]+dp_table[j-3])
        dp_table[j] = max(dp_table[j-2],graph[j-1]+dp_table[j-3])+graph[j]
        # print(j,dp_table[j-1],dp_table[j])
        dp_table[j] = max(dp_table[j],dp_table[j-1])

    # print(graph)
    # print((dp_table))
    print(dp_table[-1])

3. 문제 풀이

이 문제는 함정이 있었다. 이전에 계단오르기 문제가 있었는데 이 땐, 1칸씩오르거나 2칸씩 오르는 규칙이 있었다. 그러나 이 문제에선 연속 3번 포도주 잔을 선택하면 안된다고 했을 뿐이지, 사실 연속해서 잔을 선택하지 않아도 되는 경우가 있다.

그러다보니 내 점화식은 원래 다음과 같았다.

\[dp\_table[i] = max(dp\_table[j-2], \\graph[j-1]+dp\_table[j-3])+graph[j])\]

그러나 dp table에서 포도잔을 선택해나갈때마다 가장 최대 값들이 저장되어 있어야 했는데, 백준의 예제로 값을 확인해보니 좀 이상했다.

[0, 6, 16, 23, 28, 33, 32]

분명 제일 마지막 잔까지 확인하게되면 dp table의 마지막 값은 최대 값을 도출해야했다. 그런데 그렇지 못했다는게 좀 이상했다. 왜그런지 몰랐으나, 규칙에 꼭 연속해야한다는 보장이 없다는 것을 인터넷 검색을 통해 알게 되었다. 그래서 다음과 같은 점화식을 한번 더 추가해주어야 했다.

\[dp\_table[j] = max(dp\_table[j], dp\_table[j-1])\]

그랬더니 결과는 다음과 같았다.

[0, 6, 16, 23, 28, 33, 33]

왜 이렇게 해야하냐면, 현재 구한 dp table의 값(j번째)이 이전 dp table(j-1번째)보다 작을 수 있기 때문에 이땐 굳이 갱신할 필요가 없는 것이다. 즉, 꼭 해당 j번째 잔을 선택하지 말고 j-1번째 잔까지만 선택하자라는 의미가 된다.

이번 기회에 규칙 과 dp table의 값을 꼭 항상 확인하고 곱씹어봐야 함을 다시한번 깨닫게 되었다.