[Baekjoon][Python] 2156번 포도주 시식

2156번 포도주 시식

문제

풀이

이 문제는 앞에 포스팅한 2579번 문제와 매우 유사한 문제이다.
2579번 문제 포스팅
동일하게 DP를 이용하여 문제를 해결하면 된다.

앞의 문제와의 차이점이자 유의할 점은 다음과 같다.

1. 앞의 문제와 동일하게 3개를 연속하여 고를 순 없다
2. 하지만 앞의 문제와 다르게 2개 이상 건너뛸 수 있다.

위의 조건들을 유의하여 생각해보면 코드에 딱 하나만 추가하면 된다.
바로 dp배열의 이전 값을 최대값 선택에 넣는 것이다. 이렇게 하여 만약 dp[i-1]이 최대값으로 선택된다면, 해당 위치의 와인은 선택하지 않는 것으로 해석할 수 있다.
나머지는 동일하다.

이러한 형식으로 코드를 짜면 아래와 같다.

import sys

def operateDP(n):
    scores = [0]
    dp = [0]
    for _ in range(N):
        scores.append(int(input()))

    dp.append(scores[1])

    if N > 1:
        dp.append(dp[1] + scores[2])

    for i in range(3, N + 1):
        dp.append(max(dp[i - 1], dp[i - 2] + scores[i], dp[i - 3] + scores[i - 1] + scores[i]))
    return dp[n]

input = sys.stdin.readline

N = int(input())

print(operateDP(N))

결론

역시 DP 문제는 유사한 면이 큰 거 같다. 앞으로도 꾸준히 연습하여 익숙해지도록 해야겠다. 이 코드 역시 처음에 혼자 작성했을 때에는 매우 더러운 코드였지만, 개념을 확실히 이해하고 난 뒤에는 훨씬 코드 작성이 간결해졌다.