[백준 - 2156] 포도주 시식 문제 풀이

백준 2156번 포도주 시식 문제를 풀었다.

마시는 포도주 양의 최댓값을 구하는 문제다. 문제를 보자마자 DP로 풀 수 있겠다는 생각이 들었다.

상태를 나누기

포도주 배열을 grape, 길이를 n이라고 하자.

• n == 1이면 grape[0]
• n == 2이면 grape[0] + grape[1]

n >= 3부터는 연속으로 두 잔까지만 마실 수 있다는 조건을 봐야 한다. 그래서 i번째에서 연속으로 마시고 있는 횟수를 0, 1, 2 세 상태로 나눴다.

• 0: 이번 잔을 마시지 않는 경우이므로, 이전 세 상태 중 최댓값을 가져온다.
• 1: 직전에 마시지 않은 상태에서 이번 잔을 마신다.
• 2: 직전에 한 잔을 마신 상태에서 이번 잔을 더 마신다.

점화식은 아래처럼 잡았다.

dp[index][continueNum]
dp[index][0] = max(dp[index - 1][0], dp[index - 1][1], dp[index - 1][2])
dp[index][1] = dp[index - 1][0] + grape[index]
dp[index][2] = dp[index - 1][1] + grape[index]

코드

n = int(input())

grape = []
for _ in range(n):
    grape.append(int(input()))

if n == 1:
    print(grape[0])
elif n == 2:
    print(grape[0] + grape[1])
else:
    dp = [[0 for _ in range(3)] for _ in range(n)]

    dp[0][1] = grape[0]
    dp[0][2] = grape[0]
    dp[1][0] = grape[0]
    dp[1][1] = grape[1]
    dp[1][2] = grape[0] + grape[1]

    for i in range(2, n):
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = dp[i - 1][0] + grape[i]
        dp[i][2] = dp[i - 1][1] + grape[i]

    print(max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))

이렇게 포도주 시식 문제를 해결했다.

원문: Velog에서 보기