https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
#include <stdio.h>
int dp[10005] = {0};
int arr[10005] = {0};
int max(int a, int b){ return a>b?a:b; }
int main(){
int n;
scanf("%d", &n);
for(int i=3; i<n+3; i++) scanf("%d", &arr[i]);
for(int i=3; i<n+3; i++){
dp[i] = max(dp[i-1], max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i]));
}
printf("%d", dp[n+2]);
return 0;
} 값들을 입력받을때 세그멘테이션 폴트때문에 i를 3부터 시작했다.
i번째 포도주에 관련한 경우는 크게 세가지로 나뉘는데,
첫번째는 마시지 않고 지나가는것이다.
이 경우에는 바로 전에 계산된값과 전혀 다르지 않으므로
dp[i-1]의 값이 될 것이다.
두번째는 두번 연속으로 마시는 경우이다.
두번째를 위해서 모든 경우들은 무조건 처음에 한 번은 안마시고간다는 내용이 있어야 한다.
그렇지 않다면 두번 연속으로 먹기 + 한번 더먹기 등의 조합이 가능해져
문제의 조건에 위배된다.
따라서 dp[i-3]을 마시고, [i-2]번은 마시지 않고 건너뛰니 계산하지 않은 다음,
arr[i-1]번과 arr[i]번을 순서대로 마신다.
세번째는 한번만 마시는 경우다.
두번째에 의해서 dp[i-2]를 한번 마시고,
[i-1]번은 마시지 않으며
arr[i]번을 마신다.
이 세가지 경우 중의 최대값이 dp[i]번을 마실때의 최대값이 될 것이고,
dp[n+2]번을 통해 모든 계산을 끝낸 후의 최대값에 접근할 수 있다.
출력하면 문제 해결.
반응형