백준 2156 - 포도주 시식

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

접근법

뭔가 딱봐도 DP로 접근해야 할 것 같았음

일단 연속 2잔까지만 마실 수 있다는 점 + 예시에서 보면 가장 큰 13이라는 수를 선택 안했을 경우 값이 최대가 나온다는 걸 봤을 때 꼭 큰 수를 골라야 한다는 건 아니라는 걸 알겠음

일단 쪼개서 잔의 개수가 1~3개 있는 경우를 우선 생각해 보면

잔 = 1 / 그냥 그 잔 한이 최댓값

잔 = 2 / 첫번째 + 두번째

잔 = 3 / 첫번째+두번째 or 두번째+세번째 or 첫번째+세번째 중에서 가장 큰 값 (최대치이기 때문에 안마시고 존버하는 경우는 고려 안해도 될것 같음)

잔 =4의 경우를 보면

1	2	3	4
X	O	O	X
O	X	O	X
O	O	X	X

만약에 네번째를 안 마신다고 가정했을 때, 1 2 3번이 생각해보면 위에서 잔=3일 때 한 고민과 똑같다는 걸 알 수 있음

1	2	3	4
O	O	X	O
O	X	O	O

이번에는 네번째를 마신다고 가정해보면, (물론 경우의 수는 더 있겠지만 최댓값을 구하는 거기 때문에 가능한 한 많이 마시는 경우만 생각함)
3번째를 O - 2번째를 X - 1번째를 O
or 3번째를 X - 1번째를 O +2번째를 O

그러면 이제 점화식을 세울 수 있는데,
dp[i] = i번째까지 마실 수 있는 최댓값
dp[1~3]까지를 기본값으로 설정할 수 있고, 네번째부터 식을 세워보면

1) dp[3] - 네번째를 안 마신다고 가정했을 때 최댓값

2) dp[2] + 포도주[4] - 세번째를 안 마시기 때문에 두번째까지의 최댓값 + 네번째 포도주

3) dp[1] + 포도주[3] + 포도주[4] - 두번째를 안 마시기 때문에 첫번째까지의 최댓값 + 세번째 + 네번째

이제 이걸 반복문에 넣게 i로만 바꿔주면 됨

Code.

const fs = require("fs");
let input = fs
  .readFileSync("./test.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => +v);
const len = input[0];
const dp = Array(len + 1).fill(0);
dp[1] = input[1];
dp[2] = input[1] + input[2];
dp[3] = Math.max(input[1] + input[2], input[2] + input[3], input[1] + input[3]);
for (let i = 4; i <= len; i++) {
  dp[i] = Math.max(
    dp[i - 1],
    dp[i - 2] + input[i],
    dp[i - 3] + input[i - 1] + input[i]
  );
}
console.log(dp[len]);

점화식 세울 때 항상 작은 값에서부터 시작하기가 왜 중요한지 알 수 있는 좋은시간...