[Algorithm] 2156. 포도주 시식

2156: 포도주 시식(DP)

https://www.acmicpc.net/problem/2156

• 문제 티어 : S1
• 풀이 여부 : Failed → Solved
• 소요 시간 : 17:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = [0] + [int(input()) for _ in range(N)] # 1부터 시작하기 위해 [0] 추가
dp = [0 for _ in range(N+1)]

dp[1] = arr[1]
if N > 1:
  dp[2] = arr[1] + arr[2]

for i in range(3, N+1):
  dp[i] = max(
    dp[i-1], # 현재 잔을 마시지 않는 경우
    dp[i-2] + arr[i], # 현재 잔을 마시고, 이전 잔은 마시지 않는 경우
    dp[i-3] + arr[i-1] + arr[i] # 현재 잔과 바로 이전 잔을 마시고, 그 이전 잔을 마시지 않는 경우
  )

print(dp[N])

접근 방식

• basecase
  • dp[0] = 0 → 포도주가 없는 경우
  • dp[1] = arr[1] → 첫번째 포도주만 있는 경우
  • dp[2] = arr[1] + arr[2] → 첫번째 두번째 포도주만 있는 경우

→ 위 세 경우가 “연속된 세 잔을 모두 마실 수 없다”의 조건을 언제든 충족하는 경우이므로 basecase로 설정

3~N까지 dp를 갱신하면서,

1) 현재 잔을 마시지 않는 경우: dp[i-1] (arr[i]를 더하지 않고 dp[i-1]이전 상태를 그대로 가져감)

2) 현재 잔을 마시고, 이전 잔은 마시지 않는 경우: dp[i-2] + arr[i]

3) 현재 잔과 바로 이전 잔을 마시고, 그 이전 잔은 마시지 않는 경우: dp[i-3] + arr[i-1] + arr[i]

ex) i = 3 → dp[0] + arr[2] + arr[3]

위 3개의 값 중 최댓값을 찾아 갱신

접근 시행착오(+ 코드)

처음에는 배열을 순회하면서 가장 많은 포도주를 마실 수 있는 방법을 그때 그때 선택하는 그리디로 접근하려고 했다. 하지만, 문제 조건 중 "연속된 세 잔을 모두 마실 수 없다”로 인해 초기에 몇 가지 잔을 선택하는 것이 나중에 더 많은 양을 마실 기회를 상실할 수 있다.

즉, 초기 선택이 후반부의 선택에 영향을 미치며, 이는 그리디 알고리즘으로는 전체 최적 해를 찾을 수 없음을 의미한다.

따라서 DP를 사용해 각 단계의 선택이 전체 해에 미치는 영향을 고려해서, 모든 가능한 선택을 고려하고, 그 중에서 최적의 해를 찾도록 했다.

배운점 또는 느낀점

당연히 그리디라고 생각하고 풀이했는데, DP였다.

각 단계의 최적해가 전체 문제의 최적해를 만들 수 없는 문제는 DP를 고려해서 풀어보자!