백준 2156번: 포도주 시식 - javascript

백준 2156번: 포도주 시식

문제 설명

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

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

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

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

접근

포도주를 3번 연속으로 마실 수 없다는 조건하에 나올 수 있는 규칙을 생각해보았다.

• 먹고 -> 먹고 -> 안먹고 -> 먹고…
• 먹고 -> 안먹고 -> 먹고…
• 안먹고 -> 먹고 ->…
• 안먹고 -> 안먹고 ->…

이렇게 4가지정도 경우가 나온다.
맨날 실수하는건데 이 규칙을 또 1번째부터 n번째까지 미래진행형으로 풀어서 시간만 날렸다…
막 if(i < i+1 && count < 3) …이런식으로 말이다. 현재를 정하는건 과거에 기반해야되는데 자꾸 문제를 풀 때마다 현재를 기반으로 미래를 고르려고한다. 다시 문제로 돌아와서, 과거에 기반해서 현재를 정하려면 이전에 먹었는지 안먹었는지가 중요하다.
중요한가?..
내가 지금 2번째 잔인지 3번째 잔인지 구분하는데 있어서 별도의 카운터를 마련할까 생각했는데, 다른 사람들이 푼 방식을 보니깐 그냥 그 조건조차도 점화식에 넣어버리면 되는거였다.
dp문제는 익숙해졌다고 생각하면 다음 문제에서 이렇게 막혀버린다..

풀이법은 그냥 현재 n번째는 과거에 대해 2가지 선택을 하면 된다.
n = 지금먹고 + (n-1)번째는 안먹고 + (n-2)번째까지의 최대선택값(먹고) 혹은
n = 지금먹고 + (n-1)번째도 먹고 + (n-2)번째는 안먹고 + (n-3)번째까지의 최대 선택값(먹고) 이렇게 먹는것으로 시작하는 2가지 조건을 나타낼 수 있다.

위는 현재 먹는다는 선택을 하는 경우고, 이번엔 현재에 안먹는의 경우를 생각해봐야되는데…
안먹는건 n-1번째까지의 선택을 그대로 가져온다는 거니깐 그냥 dp(n)과 dp(n-1)을 비교해서 가져오면 된다.
이걸 2번 반복하면 2연속으로 안먹는 경우도 가능하다.

dp[i] = max(dp[i-2]+원본[i], dp[i-3]+원본[i-1]+원본[i]) //현재 먹는경우
dp[i] = max(dp[i-1], dp[i]) //만약 현재 안먹는경우

최종적으로는 이런형태의 점화식을 얻을 수 있다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [0,0,0];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer = '';
  let n = input.splice(3,1);
  answer = wine(n*1,input)
  console.log(answer)
  process.exit();
});

function wine(n, arr){
  let answer = 0;
  let dp = new Array(n+3).fill(0);  
  for(let i=3;i<n+3;i++){    
    dp[i] = Math.max(dp[i-3]+arr[i-1]*1+arr[i]*1, dp[i-2]+arr[i]*1);
    dp[i] = Math.max(dp[i-1], dp[i]);    
    answer = Math.max(answer, dp[i]);
  }  
  return answer;
}