[문제]
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
[풀이]
시식할 수 있는 포도주의 최대 양을 구하는 문제.
단, 연속해서 3잔을 마실 수 없다.
점화식을 세워서 DP를 통해 해결했다.
DP[x]는 x잔 마시는데 마실 수 있는 최대 포도주의 양을 저장하는 배열이다.
연속해서 3잔을 마실 수 없으므로 아래와 같이 점화시을 유도할 수 있다.
DP[x]= max(DP[x-3]+arr[x-1]+arr[x] , DP[x-2]+arr[x]);
하지만 예외가 있어서 따로 처리해줘야 된다.
예를 들어 포도주의 양이 1,1,1,10,500,1인 경우 위의 식에 의하면 최댓값은 502가 된다.
하지만 1,1,10,500으로 마실 수 있으므로 최댓값은 512이다.
따라서 이러한 경우의 예외처리를 위해 아래의 식도 추가해줘야 된다.
DP[x]= max(DP[x],DP[x-1]);
[코드]
시간 : 4ms
#include <iostream>
#define MAX 10001
using namespace std;
int DP[MAX]={0,};
int arr[MAX]={0,};
int N;
int max(int a , int b)
{
if (a> b) return a;
else return b;
}
int main(void)
{
cin >> N;
for(int i=1;i<=N;i++) cin >> arr[i];
DP[1] = arr[1];
DP[2] = DP[1] + arr[2];
for(int i=3;i<=N;i++){
DP[i] = max(arr[i]+arr[i-1]+DP[i-3] , arr[i]+DP[i-2]);
DP[i] = max(DP[i], DP[i-1]);
}
cout << DP[N];
return 0;
}