포도주 시식

문제

• 백준 2156번 - 포도주 시식

언어

• JavaScript

문제 풀이 step 1

• dp[n] = n 개의 포도주 중에서 최대로 마실 수 있는 포도주의 양
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• n 번째에 경우의 수는 2가지 입니다.
  • n 번째 포도주를 마신다. (3잔 연속은 마실 수 없으니 이 경우 안에 2 가지 경우가 또 있다.)
    • dp[n] = wines[i] + dp[i - 2] (이전 이전에 마신 경우)
    • dp[n] = wines[i] + dp[i - 1] + dp[i - 3] (이전에 마시고, 이전 이전 이전에 마신 경우)
  • n 번째 포도주를 마시지 않는다.
    • dp[n] = dp[n - 1]
• 최종적으로, dp[n] 이 정답이 됩니다.

후기

• 꼭 다시 풀어볼 문제입니다.
• 처음에는 dp[n]을 n 번째 포도주를 무조건 마시는 경우의 최대 포도주 양으로 했습니다.
• 하지만 이렇게 하니까 답이 나오질 않았습니다.
• 안 마시는 경우도 고려하는 점화식과 마시는 경우만 고려하는 점화식의 차이는 뭘까 고민했습니다.
  • 예상으로는 연속해서 3잔을 마실 수 없기 때문에 두 점화식에 차이가 있는 것 같습니다.
• 다시 풀어봤는데, 똑같은 실수를 하였습니다.
  • 조금 구글링을 해보니, 포도주를 2 번 연속으로 안먹는 경우가 반례로 존재해서 그런거였습니다.
  • 그래서 포도주를 안먹는 경우도 고려해서 점화식을 전개하면 해당 반례도 고려할 수 있기 때문에 풀리는 것이였습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	let n = parseInt(input[0]);
	const wines = input.slice(1, n + 1).map(Number);

	// index 처리를 더 가독성 있게 하기 위해서
	wines.unshift(0);

	if (n === 1) return wines[1];

	const dp = [];
	// base
	dp[0] = 0;
	dp[1] = wines[1];
	dp[2] = wines[1] + wines[2];

	for (let i = 3; i < n + 1; i++) {
		dp[i] = Math.max(
			dp[i - 1],
			wines[i] + dp[i - 2],
			wines[i] + wines[i - 1] + dp[i - 3]
		);
	}

	return dp[n];
};

console.log(solution(input));