2156번 : 포도주 시식

약간 복잡한 dp테이블을 세워야 하지만 2579번 계단 오르기와 많이 비슷하다.

dp를 세울 때 i번째에 자신이 포함될 때와 포함되지 않을 때 두가지의 경우를 생각해 주면 된다. 왜냐하면 i+1, i+2에서 i번째를 포함 할지 안할지 모르기 때문이다.

dp[i][j]는 i번째에 j가 0이면 i번째를 포함하지 않는 것, 1이면 i번째를 포함하는것을 의미한다.

그렇다면 어떻게 해야할까? 

우선 dp[1][0]과 dp[1][1]은 각각 0과 arr[1]로 초기화한다.

i번째에 자신이 포함되지 않을 때는 dp[i-1][0]과 dp[i-1][1]을 비교(i-1번째 수를 포함시키는 경우와 포함시키지 않는 경우를 비교)해서 더 큰값을 이용한다.

i번째에 자신을 포함할 때는 조금 복잡해진다. 연속해서 3번을 뽑을 수 없으니 이 경우를 생각해주어야 한다.

그럼 연속해서 3번을 뽑는 것을 어떻게 알 수 있을까?

우선 i번째를 포함하는 dp를 dp[i][1] = MAX(dp[i - 1][0], dp[i - 1][1]) + arr[i]; 이렇게 채워주고 시작한다.

i를 포함하여 3번 연속이니 i-3번째는 포함되지 않으면서 i-2, i-1, i번째가 포함된다는 소리다.

즉 dp[i][1]이 dp[i-3][0] + arr[i-2] + arr[i-1] + arr[i]가 되는 순간이 3번 연달아 포함한 경우이다.

위 조건을 만족하면 dp[i][1]을 바꾸어줘야한다.

이것은 두가지 경우로 판단할 수 있다. 1) i-2번째를 포함하지 않는 경우, 그리고  2) i-1번째를 포함하지 않는 경우.

1) i-2번째를 포함하지 않고 i-1번째와 i번째를 포함할 때는 dp[i-2][0] + arr[i-1] + arr[i]의 식이 만들어진다.

2) i-1번째를 포함하지 않고 i번째를 포함할 때는 dp[i-1][0] + arr[i]의 식이 만들어진다.

1)과 2) 중 더 큰수를 택한 것이 dp[i][1]이 된다.

출력을 할 때는 N번째 포도주를 선택할 때와 선택하지 않을 때 중 더 큰값으로 출력하면 된다. 즉 dp[N][0]과 dp[N][1] 중 더 큰값을 출력하면 된다.

#include <stdio.h>

int N, dp[10001][2], arr[10001];

int MAX(int a, int b) {

return a > b ? a : b;

}

int main() {

scanf("%d", &N);

for (int i = 1; i <= N; ++i) {

scanf("%d", &arr[i]);

}

dp[0][0] = 0;

dp[0][1] = 0;

dp[1][0] = 0;

dp[1][1] = arr[1];

for (int i = 2; i <= N; ++i) {

dp[i][0] = MAX(dp[i - 1][0], dp[i - 1][1]);

dp[i][1] = MAX(dp[i - 1][0], dp[i - 1][1]) + arr[i];

if (i >= 3 && (dp[i][1] == dp[i - 3][0] + arr[i - 2] + arr[i - 1] + arr[i])) {

dp[i][1] = MAX(dp[i - 2][0]+arr[i-1], dp[i - 1][0]) + arr[i];

}

}

printf("%d", MAX(dp[N][0],dp[N][1]));

}