[백준 2156번] 포도주 시식

문제

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

2156번: 포도주 시식

---

풀이

아이디어

• DP 개념: 2023.08.27 - [Algorithms/이코테] - [Dynamic Programming] - 다이나믹 프로그래밍이란? / 문제 1로 만들기

 

# 포도주 잔의 개수 입력 받기
n = int(input())

# 포도주 list 입력 받기 + 여유 인덱스로 1 ~ n으로 맞춰주기
k = [0] + [int(input()) for _ in range(n)] + [0]
print(k)

# dp 초기화
dp = [0] * (n+2)

# dp 첫 번째 값 = 첫 번째 포도주 양
dp[1] = k[1]
# dp 두 번째 값 = 첫 번째 포도주 양 + 두 번째 포도주 양
dp[2] = dp[1] + k[2]

# DP 보텀업 진행
# 연속으로 3잔을 모두 고를 수 없다는 것을 고려해
# i - 1잔을 마시지 않은 경우 => dp[n] = dp[i - 2] + k[i]
# i - 1잔을 마신 경우 => dp[n] = dp[i - 3] + k[i - 1] + k[i] 
for i in range(3, n+1):
  dp[i] = max(dp[i - 3] + k[i - 1] + k[i], dp[i - 2] + k[i])
  # 포도주를 연속으로 2번 안먹을 경우 고려 => 이전 값과 현재 값 비교
  dp[i] = max(dp[i - 1], dp[i])

print(dp[n])

1로 만들기 문제처럼 반복문을 이용해 작은 문제부터 차근차근 답을 도출하는 보텀업 방식 DP풀이이다.

최대로 마실 수 있는 포도주의 양을 구하는 문제로

1.  (3번째 포도주부터) 현재 마시는 포도주가 k[i]일 때, 이전 포도주 k[i - 1]을 먹었다면 => dp[n] = dp[i - 3] + k[i - 1] + k[i] 

2. 이전 포도주 k[i - 1]를 먹지 않았다면 => dp[n] = dp[i - 2] + k[i]이 된다.

1, 2를 비교해 더 큰 값을 찾아나가면 된다.

3. 포도주를 연속해서 2번을 마시지 않는 경우도 고려해준다. dp[i] = max(dp[i - 1], dp[i])

 

 

---

 

참고

https://mygumi.tistory.com/98

 

 

🙂 공부하며 정리하는 글입니다. 잘못된 점이 있다면 피드백 남겨주세요.