2156 포도주 시식

문제 분석

알고리즘: DP

포도주를 마시는 경우의 수를 생각해보면, 다음과 같이 세가지 경우가 있다.

1. N-1번째 포두주를 마시지 않고 N-3번째, N-1번째, N번째 포도주를 마신 경우
   즉, N-3 까지 마신 최고 용량 + N-1번째 포도주 양 + N번째 포도주 양

2. N-1번째 포두주를 마시지 않고 N-2번째, N번째 포도주를 마신 경우
   즉, N-2 까지 마신 최고 용량 + N번째 포도주 양

3. N-1번째 포두주를 마시고 N번째 포도주를 마시지 않은 경우
   즉, N-1 까지 마신 최고 용량

표로 보기쉽게 표현하면 다음과 같다. (마셨을 경우 O, 마시지 않았을 경우 X)

…	N-3 번째	N-2 번째	N-1 번째	N 번째
1	O	X	O	O
2	…	O	X	O
3	…	…	O	X

위 경우들을 점화식으로 나타내보자.

DP는 답을 할당할 배열, WINE은 포도주 잔을 표현

1. DP[N] = DP[N-3] + WINE[N-1] + WINE[N];
2. DP[N] = DP[N-2] + WINE[N];
3. DP[N] = DP[N-1];

따라서 최대로 마실 수 있는 포도주의 양을 구하기 위해 위 세가지 경우 중 가장 결과값이 큰 경우의 결과를 DP에 저장해주면 된다.

풀이

const [N, ...a] = require('fs')
  .readFileSync('dev/stdin')
  .toString()
  .split('\n')
  .map(Number);
const dp = new Array(N).fill(0);

dp[0] = a[0];
dp[1] = a[0] + a[1];
dp[2] = Math.max(a[0] + a[2], a[1] + a[2], dp[1]);

for (let i = 3; i < N; i++) {
  dp[i] = Math.max(dp[i - 2] + a[i], dp[i - 3] + a[i - 1] + a[i], dp[i - 1]);
}
console.log(dp[N - 1]);

느낀점

아직 DP 알고리즘에 익숙하지 않아 처음 문제를 보았을 때 DP 문제라는 것을 파악하는게 많이 더디다. DP의 원리를 이해하고는 있으나 응용하기까지의 과정이 매우 어렵게 느껴진다.

이 문제는 다른 사람들의 풀이를 구글링해보아도 바로 이해가 가지 않았고, 이해하기까지 이틀이 걸렸다. 나한테는 특히나 어려웠던 문제였다. 하지만 이 문제를 통해서 응용력이 조금은 늘지 않았을까 하는 생각이 든다.