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

import sys
sys.stdin = open("input.txt")
n = int(sys.stdin.readline().rstrip())
wine = []
for _ in range(n):
wine.append(int(sys.stdin.readline().rstrip()))
dp = [0] * (n+1)
dp[0] = wine[0]
if n > 1:
dp[1] = wine[0] + wine[1]
if n > 2:
dp[2] = max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2])
for i in range(3, n):
dp[i] = max(
dp[i-2] + wine[i],
dp[i-3] + wine[i-1] + wine[i],
dp[i-1]
)
print(max(dp))
알고리즘 분류:
- 다이나믹 프로그래밍
Key Points:
DP 유형으로 자주 나오는 계단 건너기 문제와 비슷한 듯 다르다. 우선 dp[i]는 i번째 포도주까지 시도한 상황에서 마실 수 있는 최대의 포도주 양이다. 3잔을 연속으로 마실 수 없기 때문에 i번째 포도주를 마주한 상황에서 생길 수 있는 상황은 총 세 가지이다.
1. 전전까지의 포도주 최댓값 + 현재 포도주
2. 전전전까지의 포도주 최댓값 + 이전 포도주 + 현재 포도주
3. 전까지의 포도주 최댓값 (현재 포도주 버림)
이 세 가지 상황 중 최댓값을 취하면서 계속 진행하면 된다. 처음에는 이렇게 상황을 다 따지기 시작하면 결국 상황 별로 예외를 다 생각해야 하나... 했지만 이 세 가지 상황으로 모든 경우의 수가 커버된다.
여기서 중요한 건 1번 상황과 2번 상황을 보았을 때, 각각 전전 포도주, 전전전 포도주를 마셨는지 안 마셨는지 정확히 알 수는 없지만 일단 최댓값이 적혀있을테니, 연속된 3잔을 마시는 상황을 피하기 위해서 전전 포도주와 전전전 포도주를 마셨다고 가정한 상태로 진행한다는 것이다.
이게 사실 글로 적으면 이렇게 세 가지의 상황이 나온다는 걸 알기는 알겠는데 정작 머리로 생각하려고 하면 뒤죽박죽 꼬이기 시작하고, 예외 상황이 자꾸 생각나서 결국 길을 잃는다... DP 어렵다...
'Algorithm - Python으로 다시 > DP' 카테고리의 다른 글
| [백준] 11727번: 2xn 타일링 2 (직접 점화식 찾기 2) (0) | 2024.07.24 |
|---|---|
| [백준] 11726번: 2xn 타일링 (점화식 직접 찾기) (0) | 2024.07.23 |
| [백준] 1912번: 연속합 (이전까지의 합과 현재값 비교 DP) (3) | 2024.07.22 |
| [백준] 9095번: 1, 2, 3 더하기 (직접 점화식 찾기) (0) | 2024.07.22 |
| [백준] 1463번: 1로 만들기 (dp의 기본) (0) | 2024.07.20 |