백준 1309 동물원 - node.js

해당 포스팅은 백준 1309번 동물원 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

1. 문제 설명

동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

• 사자들을 우리에 가둘 때 가로로도 세로로도 붙어 있게 배치할 수는 없다.
• 2xN 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성하자.
• 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

2. 입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

3. 출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이

해당 문제는 i번째 행에 사자를 배치하는 데에는 i-1번째 행의 배치 상태에 따라 달려있으므로 DP로 해결할 수 있다.

로직

예제를 통해 자세하게 설명하겠다. N이 3라고 가정해보자.

• [N = 0] 문제에서 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정하므로 경우의 수는 1이다.
• [N = 1] "비어있다", "왼쪽 사자", "오른쪽 사자"로 총 3가지 경우의 수가 있다.

• [N = 3] 경우의 수 7가지

  • N-1번째 줄, 즉 1번째 줄이 비어있을 때 가능한 경우의 수 = 3가지

    • 1번째 줄이 비어있다는 말은 0번째 줄에 대해서 가능한 경우의 수를 구한다는 의미이다.
    • N이 0일 때의 경우의 수는 1이다.
    • 위의 줄이 비어있으므로, N번째 줄에 대해 가능한 경우는 “비어있음”, “왼쪽 사자”, “오른쪽 사자”로 총 3가지이다.
    • 따라서 N-1번째 줄이 비어있을 때 가능한 경우의 수는 1*3 = 3가지이다.

  • N-1번째 줄, 즉 1번째 줄이 비어있지 않을 때 가능한 경우의 수 = 4가지

    • 1번째 줄이 비어있지 않다는 말은 곧 “N-1의 경우의 수 - 위의 줄이 비어있는 경우의 수”에 대해 고려한다는 말이다.
    • N-1의 경우의 수 = D[2] = 3
    • 위의 줄이 비어있는 경우의 수 = D[1] = 1
    • 위의 줄이 비어있으므로 N번째 줄에 대해 가능한 경우는 각각 2가지이다. (비어있거나 대각선 방향)
    • 따라서 N-1번째 줄이 비어있지 않을 때 가능한 경우의 수는 (3-1)*2 = 4가지이다.

  • 따라서 N이 3일 때 총 경우의 수는 3+4 = 7가지이다.

• [N = 4] 경우의 수 17가지

  • N-1번째 줄, 즉 2번째 줄이 비어있을 때 가능한 경우의 수 = 9가지

    • 2번째 줄이 비어있다는 말은 1번째 줄에 대해서 가능한 경우의 수를 구한다는 의미이다.
    • N이 1일 때의 경우의 수는 3이다.
    • 위의 줄이 비어있으므로, N번째 줄에 대해 가능한 경우는 “비어있음”, “왼쪽 사자”, “오른쪽 사자”로 총 3가지이다.
    • 따라서 N-1번째 줄이 비어있을 때 가능한 경우의 수는 3*3 = 9가지이다.

  • N-1번째 줄, 즉 2번째 줄이 비어있지 않을 때 가능한 경우의 수 = 8가지

    • 1번째 줄이 비어있지 않다는 말은 곧 “N-1의 경우의 수 - 위의 줄이 비어있는 경우의 수”에 대해 고려한다는 말이다.
    • N-1의 경우의 수 = D[2] = 7
    • 위의 줄이 비어있는 경우의 수 = D[1] = 3
    • 위의 줄이 비어있으므로 N번째 줄에 대해 가능한 경우는 각각 2가지이다. (비어있거나 대각선 방향)
    • 따라서 N-1번째 줄이 비어있지 않을 때 가능한 경우의 수는 (7-3)*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]);