[백준 2156] 포도주 시식
February 21, 2023
문제
https://www.acmicpc.net/problem/2156
아이디어
이전에 풀었던 계단 오르기와 유사한 문제이다.
다만, 계단 오르기는 한 계단을 밟으면서 이어서 다음 계단으로 오를수 있기에 반드시 해당 계단을 밟은 상태를 가정해서 계산해야 했지만, 이 문제는 현재 선택한 포도주를 반드시 마시지 않아도 되기에 그 점을 고려해서 계산해야 한다.
- 첫번째 포도주까지의 최대값은 무조건 첫번째 포도주를 마셨을 때의 값이다.
- 두번째 포도주까지의 최대값은 무조건 첫번째와 두번째 포도주를 마셨을 때의 값이다.
-
세번째 포도주까지의 최대값은 다음 세 가지의 경우의 수에서의 최대 값이다.
- 첫번째와 세번째 포도주를 마실 경우
- 두번째와 세번째 포도주를 마실 경우
- 세번째 포도주를 마시지 않고 첫번째와 두번째 포도주를 마신 채로 진행할 경우
-
마찬가지로 i번째 포도주까지의 최대값은 다음 세 가지의 경우의 수에서의 최대 값이다.
- i-3까지의 최대값에 i-1번째 포도주, i번째 포도주를 선택해서 마실 경우
- i-2까지의 최대값에 i번째 포도주를 선택해서 마실 경우
- i번째 포도주를 마시지 않고 i-1까지의 최대값으로 진행할 경우
소스코드
// 입력 처리
const INPUT_NAME = "i2.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const arr = input.slice(1, n + 1).map(e => Number(e));
const dp = Array.from({ length: n }, () => 0);
dp[0] = arr[0]; // 첫번째 포도주까지의 최대값
dp[1] = arr[0] + arr[1]; // 두번째 포도주까지의 최대값
dp[2] = Math.max(arr[0] + arr[2], arr[1] + arr[2], dp[1]); // 세번째 포도주까지의 최대값
// 문제
function solution() {
for (let i = 3; i < n; i++) {
dp[i] = Math.max(
dp[i-3] + arr[i-1] + arr[i], // i-3번째까지의 최대값에 i-1번째, i번째를 와인을 선택할 경우
dp[i-2] + arr[i], // i-2번째까지의 최대값에 i번째 와인을 선택할 경우
dp[i-1] // i번째 와인을 선택하지 않는 경우
);
}
console.log(dp[n-1]);
}
// 실행
solution();