해당 포스팅은 백준 1309번 동물원 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.
해당 문제는 i번째 행
에 사자를 배치하는 데에는 i-1번째 행
의 배치 상태에 따라 달려있으므로 DP로 해결할 수 있다.
예제를 통해 자세하게 설명하겠다. N이 3라고 가정해보자.
[N = 0]
문제에서 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정하므로 경우의 수는 1이다.[N = 1]
"비어있다", "왼쪽 사자", "오른쪽 사자"로 총 3가지 경우의 수가 있다.[N = 3]
경우의 수 7가지N-1번째 줄, 즉 1번째 줄이 비어있을 때
가능한 경우의 수 = 3가지
1*3 = 3가지
이다.N-1번째 줄, 즉 1번째 줄이 비어있지 않을 때
가능한 경우의 수 = 4가지
(3-1)*2 = 4가지
이다.따라서 N이 3일 때 총 경우의 수는 3+4 = 7
가지이다.
[N = 4]
경우의 수 17가지N-1번째 줄, 즉 2번째 줄이 비어있을 때
가능한 경우의 수 = 9가지
N-1번째 줄, 즉 2번째 줄이 비어있지 않을 때
가능한 경우의 수 = 8가지
따라서 N이 4일 때 총 경우의 수는 9+8 = 17
가지이다.
위의 예시를 통해 우리는 규칙을 발견할 수 있다.
점화식
D[N] = D[N-2] + D[N-1] * 2
const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);
const dp = [1, 3].concat(new Array(N - 1).fill(0));
for (let i = 2; i <= N; i++) {
dp[i] = (dp[i-2] + dp[i-1]*2) % 9901;
}
console.log(dp[N]);