https://www.acmicpc.net/problem/2156
문제
> 효주는 포도주 시식회에 갔다.
> 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다.
> 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
> 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다.
> 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고,
각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때,
효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
> 예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때,
첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.접근
연속 세잔을 마실 수 없기 때문에 규칙은 총 세가지로 볼 수 있다.
먼저 현재 잔을 마시지 않는경우다. 이는 연속 세잔에 걸리지 않으므로 앞에서 어떻게 마셨던 상관 없어서 dp(i-1)의 값을 계승한다.
다음은 현재잔을 마실 때의 두가지이다.
직전잔을 마셨으면(i-1) 그 직전잔 (i-2)는 마실 수 없기 때문에 i-3잔을 마시고 온 경우에만 가능하다. 그래서
dp(i-3)에 i-1과 i값을 더한 값이다.
그리고 직전잔을 안마시는 경우는 그 직전잔을 마시던 직직전잔을 마시던지 상관이 없다. 그래서 dp(i-2)에 i를 더한 값을 구하면 된다.
즉 dp(i-1), dp(i-2)+i, dp(i-3)+(i-1)+i 중 최대 값을 고르면 된다.
문제해결
> 각 잔에 들어있는 술의 양을 담을 cup벡터를 선언하고 잔의 수와 술의 양을 입력받는다
> dp를 계산할 벡터를 선언하고, 첫잔과 둘쨰잔에 대한 dp를 따로 정의 해준다.
> 세번째 잔부터 규칙을 적용해 계산해준다.
dp(i-1), dp(i-2)+i, dp(i-3)+(i-1)+i 중 최대 값을 고르면 된다.
>dp(n)값이 여섯잔까지의 최적의 마신양을 가지므로 이를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> cup(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> cup[i];
vector<int> dp(n + 1);
dp[1] = cup[1];
dp[2] = cup[1] + cup[2];
for (int i = 3; i <= n; i++)
{
dp[i] = max({ dp[i - 1], dp[i - 3] + cup[i - 1] + cup[i], dp[i - 2] + cup[i] });
}
cout << dp[n] << '\n';
}
후기
예전에 계단 오르기 문제를 풀어봤던 기억이 있어서 접근하기는 어렵지 않았다. 근데 제대로된 결과가 나오지않아 봤는데 지금 구하려는 기준의 잔을 마시지 않는 경우는 따지지않아서 그랬다. 즉, 꼭 현재잔을 마실 때만 구했기 때문이다.
그래서 이를 처리했더니 맞았다.
