[node.js,백준]2156 - 포도주 시식

목차

 

 

 문제

링크

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

문제

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

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

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

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

입력

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

 

출력

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

 

주저리

arrs[0] = [0] 을통해 아무것도 안한건 0임을 알려준다.

그리고 포도주의 값들은 rest에 담겨있다 해당부분은 index 배열확장없이 하였다.

포도주는 연속해서 3번을 마실 수 없다.

그리고 안마시고 넘어갈 수 있다.

3번연속 관련 문제가 있기때문에

0번, 1번, 2번 연속으로 나누어 주어야한다.

arrs[i] = i번째까지 포도주를 마셧을때, 마실수 있는 포도주의 최대의 양이다.

포도주를 0번 연속해서 마셨다면

• arrs[i-1]

포도주를 1번 연속해서 마셨다면

• arrs[i-2] + rest[i-1];

포도주를 2번 연속해서 마셨다면

• arrs[i-3] + rest[i-2] + rest[i-1];

arrs[1] = rest[0]을 넣어 한번마셨을때의 최대값

arrs[2] = rest[0] + rest[1]을 넣어 두번마셨을때의 최대값을 만들어준다.

그리고 3부터 반복하여

연속으로 마시기 이전으로 돌아가 for, if문을 반복해준다.

그리고 그중 최대값을 할당하여 최종적으로max를 구할수있게된다.

 

풀이

• 포도주 시식에서는 여러 잔의 포도주가 일렬로 놓여 있고, 포도주 잔을 선택하여 마실 수 있습니다. 규칙은 연속해서 세 잔 이상의 포도주는 마실 수 없다는 것입니다. 주어진 포도주 양을 바탕으로 최대한 많은 포도주를 마실 수 있는 방법을 찾는 문제입니다.

 초기 설정과 입력 분리

• - 입력으로 주어지는 데이터는 포도주 잔의 수와 각 잔에 들어 있는 포도주의 양입니다.
• - 배열 `arrs`를 사용하여 각 단계에서의 최대 포도주 양을 계산합니다.

 동적 계획법 적용

• 동적 계획법을 사용하여 각 포도주 잔을 선택했을 때 가능한 최대 포도주 양을 계산합니다.

 점수 계산 로직

• - 초기값 설정:
  • - `arrs[0]`: 포도주를 하나도 마시지 않는 경우, `0`
  • - `arrs[1]`: 첫 번째 포도주만 마시는 경우, `rest[0]`
  • - `arrs[2]`: 첫 번째와 두 번째 포도주를 마시는 경우, `rest[0] + rest[1]`
• - 점화식 적용:
  • - 포도주를 `i`번째까지 고려할 때, 가능한 최대 포도주 양은 다음과 같이 계산됩니다:
    • 1. `i`번째 포도주를 마시지 않는 경우: `arrs[i] = arrs[i-1]`
    • 2. `i`번째 포도주와 `i-1`번째 포도주를 마시고, `i-2`번째 포도주는 마시지 않는 경우: `arrs[i] = arrs[i-2] + rest[i-1]`
    • 3. `i`번째 포도주, `i-1`번째 포도주를 마시고, `i-3`번째까지의 최대 양을 더하는 경우: `arrs[i] = arrs[i-3] + rest[i-1] + rest[i-2]`
• - 최종 계산:
  • - `arrs[T]`에서 `T`는 포도주 잔의 수를 의미하며, 이 값이 최대 포도주 양을 나타냅니다.

 코드

// 포도주시식
var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `6
6
10
13
9
8
1`

let real = input.trim().split("\n");
let arrs = [0];

function testF(N, rest) {
    for (let i = 3; i <= N; i++) {
        arrs.push([]);
        arrs[i] = arrs[i - 1];
        if (arrs[i] < arrs[i - 2] + rest[i - 1]) {
            arrs[i] = arrs[i - 2] + rest[i - 1];
        }
        if (arrs[i] < arrs[i - 3] + rest[i - 1] + rest[i - 2]) {
            arrs[i] = arrs[i - 3] + rest[i - 1] + rest[i - 2]
        }
    }
}

function solution(real) {
    let [T, ...rest] = real;
    rest = rest.map(Number);
    arrs.push(rest[0]);
    arrs.push(rest[0] + rest[1])
    testF(Number(T), rest)
    // console.log(arrs)
    console.log(arrs[T]);
}
solution(real);