백준 2156번 - 파이썬

 

2156번: 포도주 시식

아직 백준에서만 dp문제를 접했지만, dp 문제는 항상 

이전의 값을 참고하여 문제에서 주어진 조건을 차례대로 충족해나가는 문제인 것 같다.

예를 들어, 1 ~ n 까지의 어떤 배열이 있고 + 문제에서 구하고자 하는 것과 주어진 조건 + 최댓값 구하기 문제라면,

1, 2, 3, 4,,, 까지 일 때의 최댓값을 축적해나가는 것이다. 그래서 마지막 n번째 배열에는 최종 최댓값을 구할 수 있는 것. 축적해 나가는 i 까지의 최댓값 후보는 여러개인 경우가 많고 max를 구한다. 그 경우의 수(후보들) 를 찾는 것이 곧 점화식을 찾는 길! 

이번 2156번도 그런 문제이다.

풀이

문제에서 중요한 것은 3개 연속으로 와인을 못마시는 것과, 여기서

와인을 마실 수도 있고 지나칠 수(선택 O or X)도 있다. 구체적으로 3가지 경우의 수가 있다.

# 1 : 이번 포도주를 먹고 이전 포도주를 먹지 않은 경우
# 2 : 이번 포도주를 먹고 이전 포도주도 먹은 경우
# 3 : 이번 포도주를 먹지 않아야 하는 경우
# 위 세가지 경우를 고려하여 max를 구한다.

코드

n = int(input())
w = [0]
for i in range(n):
    w.append(int(input()))
dp = [0]
dp.append(w[1])
if n > 1:# n == 2 일때
    dp.append(w[1] + w[2])
for i in range(3, n + 1):
    case1 = dp[i - 2] + w[i]
    case2 = dp[i - 3] + w[i - 1] + w[i]
    case3 = dp[i - 1]
    dp.append(max(case1, case2, case3))
print(dp[n])

 

참고자료

백준 2156번(python)