이번에 풀어본 문제는
백준 1309번 동물원 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int [][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        /*
         * dp[N][M]
         * N = 라인 수
         * M = 0 사자가 없는경우
         * M = 1 사자가 왼쪽에만 있는경우
         * M = 2 사자가 오른쪽에만 있는경우
        */

        dp = new int[N + 1][3];

        dp[1][0] = 1;
        dp[1][1] = 1;
        dp[1][2] = 1;

        // dp[N] 이 N번씩 반복
        for (int i = 2; i <= N; i++) {
            dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901;
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901;
        }

        System.out.print((dp[N][0] + dp[N][1] + dp[N][2]) % 9901);
    }
}

📝 풀이

N이 입력으로 주어질 때, N 크기의 동물원에 사자를 서로 겹치지 않게 배치하는 경우의 수를 구하는 문제입니다.
dp를 사용하여 풀이했습니다.
dp[N][M]에서 N은 주어진 입력크기를 나타내며
M = 0 사자가 없는경우
M = 1 사자가 왼쪽에만 있는경우
M = 2 사자가 오른쪽에만 있는경우
를 나타냅니다.
따라서 해당 조건으로 N까지의 모든 경우의 수를 구하면 해결할 수 있습니다.

📜 후기

dp라는 느낌은 쌔게 왔는데, 점화식을 구하지 못해서 답을 참고했습니다..
언제나 어려운 dp~