https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
dp문제는 풀 때 마다 점화식이 중요하다고 생각되어진다 역시 이번 문제도 점화식인데
이번문제의 경우 기존에 올렸던과는 다르게 3개의 후보중 하나를 뽑는 방식으로 생각해주어야 한다
그이유는 이번 문제에서 핵심적인 내용이 연속으로 3개의 포도주를 못마신다는 거였으니 그거를 이용해서 풀어야 한다
1.O O X O
2.O X O O
3.X O O X
이문제는 위에처럼 3가지 경우의 수가 존재 한다 즉 N번째 와인이 존재한다고 가정했을때 N번째 와인을 마신다고 가정했을때 첫번째로 마시냐 두번째로 마시냐 혹은 안마시냐 이렇게 3개의 경우의 수가 존대 한다. 이를 점화식으로 나타내면
1은 dp[j-2]+arr[j];
2는 dp[j-3]+arr[j-1]+arr[j]
3은 dp[j-1]
이다 1은 j번째 포도주를 먹기로 가정했기 때문에 내이전은 못마시고 나보다 2개전에 있는 애를 마실 수 있다
2는 나도 마시고 내이전도 마신다고 가정한것이다
마지막은 나를 안마셨기 때문에 나의 이전까지의 최대값만 필요하다 어차피 이렇게 우리가 3개의 식으로 나눴을 경우 3잔을 연속으로 마시는 경우의 수는 발생하지 않는다
#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001];
int arr[10001];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
dp[1] = arr[1];
dp[2] = arr[1] + arr[2];
for (int j = 3; j <= n + 1; j++) {
dp[j] = dp[j - 1];
dp[j] = max(dp[j], dp[j - 2] + arr[j]);
dp[j] = max(dp[j], dp[j - 3] + arr[j - 1] + arr[j]);
}
cout << dp[n] << endl;
}