kingsubin

import java.io.*;

public class boj_1309 {
    static int[][] dp;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int mod = 9901;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        dp = new int[n+1][3];

        dp[0][2] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][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] + dp[i-1][2];

            dp[i][0] %= mod;
            dp[i][1] %= mod;
            dp[i][2] %= mod;
        }

        int ans = (dp[n][0] + dp[n][1] + dp[n][2]) % mod;
        System.out.println(ans);
    }
}

 

- 마지막 부분에 초점을 맞춤

- dp[n+1][3] :: 0 왼쪽칸, 1 오른쪽칸 , 2 둘 다 비었을때 

- dp[n][x] -> n개의 세로 중 x번째에 사자가 있는 경우 => dp[n-1][x가 아닌수]의 합

- 초기에 전부 사자가 없는 경우도 1가지의 방법으로 해준다고 했으니 dp[0][2] = 1;

- ans는 모든 경우의 수의 합