BOJ#2156 포도주 시식

BOJ#2156 포도주 시식

* 문제

https://www.acmicpc.net/problem/2156

* 풀이

동적계획법(Dynamic Programming)을 이용해봅시다.

일단 아래와 같이 배열을 선언합니다.

dp[n] : n잔 째 마셨을 때, 최대로 마실 수 있는 포도주의 양

p[n] : 포도주 n번 째 잔에 들어있는 포도주의 양

포도주는 3번 연속해서 마실 수 없으므로,

n번 째 (마지막) 포도주는 3가지 경우로 나눌 수 있습니다.

마시지 않는 경우, 1잔 째 마신 경우, 2잔 째 마신 경우

우리가 구하려는 dp[n]을 구해봅시다.

1) 마지막 n번 째 포도주 잔 - 마시지 않는 경우

 : n-1번 째 잔은 다시 1, 2, 3번의 경우로 나누어 질 수 있습니다.

 : dp[n] = dp[n-1]

2) 마지막 n번 째 포도주 잔 - 1잔 째 마신 경우

 : n번 째 잔은 마시고, n-1번 째 잔은 안마신 것이므로

 : dp[n] = dp[n-2] + p[n]

3) 마지막 n번 째 포도주 잔 - 2잔 째 마신 경우

 : n, n-1번 째 잔은 마시고, n-2번 째 잔은 안마신 것이므로

 : dp[n] = dp[n-3] + p[n-1] + p[n]

결국 dp[n]은 3가지 경우 중 최대값을 선택하면 됩니다.

dp[n] = Max(dp[n-1], dp[n-2] + p[n], dp[n-3] + p[n-1] + p[n])

static int go(int n, int[] p) { if (n < 1) { return 0; } else if (n == 1) { return p[1]; } else if (n == 2) { return p[1] + p[2]; } if (dp[n] > 0) { return dp[n]; } dp[n] = Math.max(Math.max(go(n - 1, p), go(n - 2, p) + p[n]), go(n - 3, p) + p[n] + p[n - 1]); return dp[n]; }

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232156_WineTaste