이번 문제는 백준의 실버 1 문제 포도주 시식이다.
문제를 한 번 차근차근 읽어보자.
포도주의 양이 순서대로 주어지며, 최대 10000개가 주어진다.
이 때 포도주를 가장 많이 마실 수 있는 경우를 구해달라고 한다.
단, 3잔을 연속으로 마실 수는 없다고 한다.
만약 마지막 조건이 없었다면 그리디하게 풀 수 있었을 것이다.
하지만, 조건이 있고 최대의 포도주 양을 구해달라고 하니
Memoization을 통해서 최대 양을 갱신하며 나아가는게 좋아보인다.
DP
동적 계획법 문제는 모든 경우를 직접 적어보는 것이 중요하다.
앞에서부터 차근차근 생각해보자.
6 10 13 9 8 1로 주어진 예시를 생각해보자.
만약 가장 첫 포도주를 마신다면 6을 마신게 된다.
여기서부터 이제 분기가 갈리게 된다.
만약 두 번째 포도주를 마시게 된다면?
16을 마시게 되었으며, 13의 포도주는 마실 수 없다.
그럼 여기서 두 가지 경우가 더 발생하게 된다.
첫 번째 포도주를 안마셨으면? 23의 포도주를 마시게 된다.
두 번째 포도주를 안마셨으면? 19의 포도주를 마시게 된다.
결과적으로 현재 단계에서 아래의 세 경우를 고려할 수 있다.
- 바로 이전 포도주와 현재 포도주를 마시는 경우
- 전전 포도주와 현재 포도주를 마시는 경우
- 이전 포도주와 전전 포도주를 마셔 현재 포도주를 안 마실 경우
이를 코드로 구현하면 아래와 같이 구현할 수 있다.
int num = 0;
int wines[10001], dp[10001];
int main() {
cin >> num;
for (int i = 0; i < num; i++)
cin >> wines[i];
dp[0] = wines[0];
dp[1] = wines[0] + wines[1];
dp[2] = max(dp[1], max(wines[0] + wines[2], wines[1] + wines[2]));
// 기저 조건들은 2번까지 미리 구해놓아야 한다.
// 점화식에 dp[i-3] 까지 사용되기 때문!
for (int i = 3; i < num; i++)
dp[i] = max(dp[i - 1], max(wines[i] + dp[i - 2], wines[i] + wines[i - 1] + dp[i-3]));
cout << dp[num - 1];
return 0;
}dp[i-1]: 현재 포도주를 마시지 않는 경우wines[i] + dp[i-2]: 이전 포도주를 마시지 않는 경우wines[i] + wines[i-1] + dp[i-3]: 이전 포도주 + 현재 포도주의 경우
특이한 조건이 걸린 DP 문제였다.
역시 DP는 모든 경우의 수를 다 직접 적어보면 대부분 풀린다.