[BaekJoon] 1309번 - 동물원 [Java][C++]

문제 링크

---

1. 문제 풀이

$2 \times N$ 크기의 배열에 사자들을 배치해야 하는데 이때 사자들이 가로로도 세로로도 붙어 있게 배치할 수 없다. 이때 배치할 수 있는 모든 경우의 수를 세야하며 사자를 한 마리도 배치하지 않는 경우도 하나의 경우로 센다.

해당 문제는 다이나믹 프로그래밍을 활용하면 해결할 수 있는데 현재 사자를 배치하려는 열 번호를 $i$ 라고 했을 때, 해당 열에 사자를 배치하지 않는 경우의 수는 이전 열인 $i-1$ 번째 열에 사자를 배치하거나 배치하지 않은 경우의 수의 합이다. 현재 열에 사자를 배치하는 경우의 수는 이전 열인 $i-1$ 번째 열에서 사자를 배치하지 않았을 경우 윗 칸 또는 아랫 칸에 배치할 수 있고, 사자를 배치했을 경우 배치한 칸의 대각선 칸에 배치할 수 있다.

즉 사자를 배치하지 않는 경우의 수를 $a$, 사자를 배치하는 경우의 수를 $b$ 라고 할 때, 열 $i$ 에 사자를 배치하지 않는 경우 수는 $a_i = a_{i-1} + b_{i-1}$ 이며, 열 $i$ 에 사자를 배치하는 경우의 수는 $b_i = 2 \times a_{i-1} + b_{i-1}$ 이 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static int MOD = 9901;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[1 + n][2];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            dp[i][1] = (2 * dp[i - 1][0] + dp[i - 1][1]) % MOD;
        }

        System.out.println((dp[n][0] + dp[n][1]) % MOD);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MOD = 9901;
int dp[100001][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
        dp[i][1] = (2 * dp[i - 1][0] + dp[i - 1][1]) % MOD;
    }

    cout << (dp[n][0] + dp[n][1]) % MOD;
}

---