[BOJ 2156] 포도주 시식

문제

포도주 시식

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

 

 

풀이

설명

마실 수 있는 포도주의 최대 양을 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 합니다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없습니다.

 

BOJ 2579번 계단 오르기 문제와 유사하나, 계단 오르기 문제와 달리 마지막 잔을 꼭 선택할 필요는 없습니다.

 

마찬가지로 DP를 이용해 해결할 수 있습니다.

 

dp[i]는 i번째 포도주 잔이 마지막 잔일 때 마실 수 있는 최대 양입니다.

 

포도주의 양을 담은 배열을 wines라고 할 때,

dp[i]의 값은 다음 세 가지 중 가장 큰 값입니다.

• dp[i - 1]
• dp[i - 2] + wines[i]
• dp[i - 3] + wines[i] + wines[i - 1]

 

예시 코드

function solution() {
  const n = Number(input());
  const inputs = Array.from({ length: n }, () => Number(input()));
  const wines = [0].concat(inputs);
  const dp = [0, wines[1], wines[1] + wines[2]];
  for (let i = 3; i <= n; i++) {
    dp[i] = Math.max(
      dp[i - 1],
      dp[i - 2] + wines[i],
      dp[i - 3] + wines[i] + wines[i - 1]
    );
  }

  return dp[n];
}