동물원

문제

• 백준 1309번 - 동물원

언어

• JavaScript

문제 풀이 step 1

• dp[n][0] = 세로가 n 칸인 동물원에서 마지막에 사자를 놓지 않는 경우의 수
• dp[n][1] = 세로가 n 칸인 동물원에서 마지막에 왼쪽에 사자를 놓는 경우의 수
• dp[n][2] = 세로가 n 칸인 동물원에서 마지막에 오른쪽에 사자를 놓는 경우의 수
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• 앞의 n - 1 만큼의 과정은 완성되어 있다고 가정하고, n번째를 생각해보겠습니다.
• 경우의 수는 3가지가 나옵니다. 사자를 놓지 않는 경우, 왼쪽만 놓는 경우, 오른쪽만 놓는 경우
  • 마지막에 사자를 놓지 않는 경우는 앞에 모든 경우가 올 수 있습니다.
    • dp[n][0] = dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]
  • 마지막에 왼쪽에 사자를 놓는 경우는 앞에 비어있거나 앞에 오른쪽에 사자가 놓인 경우만 올 수 있습니다.
    • dp[n][1] = dp[n - 1][0] + dp[n - 1][2]
  • 마지막에 오른쪽에 사자를 놓는 경우는 앞에 비어있거나 앞에 왼쪽에 사자가 놓인 경우만 올 수 있습니다.
    • dp[n][2] = dp[n - 1][0] + dp[n - 1][1]
• 3 가지의 경우의 수를 모두 더한 값이 세로가 n칸인 동물원에 사자를 놓을 수 있는 경우의 수 입니다.

소스 코드

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

const solution = (input) => {
	const MOD = 9901;
	let N = parseInt(input[0]);
	const dp = Array.from({length: N + 1}, () => []);

	// base
	dp[1] = [1, 1, 1];
	for (let i = 2; i < N + 1; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
		dp[i][1] = dp[i - 1][0] + dp[i - 1][2];
		dp[i][2] = dp[i - 1][0] + dp[i - 1][1];

		for (let j = 0; j < 3; j++) {
			dp[i][j] %= MOD;
		}
	}

	return (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
};

console.log(solution(input));