[백준] 1309번 동물원 - Java, 자바

난이도

실버 1

문제

https://www.acmicpc.net/problem/1309

풀이

1. 테이블 정의하기

D[i][0] = i번째 줄에 사자가 없어도 되는 경우
D[i][1] = i번째 줄, 1번째 칸에 사자가 있는 경우
D[i][2] = i번째 줄, 2번째 칸에 사자가 있는 경우

2. 점화식 찾기

i번째 줄에 사자가 없으려면, i-1번째 줄에 사자가 없거나, 1번째 칸에 사자가 있거나 2번째 칸에 사자가 있어야 합니다.
D[i][0] = D[i-1][0] + D[i-1][1] + D[i-1][2]

i번째 줄, 1번째 칸에 사자가 있으려면, i-1번째 줄에 사자가 없거나 2번째 칸에 사자가 있어야 합니다.
D[i][1] = D[i-1][0] + D[i-1][2]

i번째 줄, 2번째 칸에 사자가 있으려면, i-1번째 줄에 사자가 없거나 1번째 칸에 사자가 있어야 합니다.
D[i][2] = D[i-1][0] + D[i-1][1]

3. 초기값 정하기

D[1][0]=D[1][1]=D[1][2]=1

코드

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

// 1309번 동물원
public class boj_3_1309 {
    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[n + 1][3];
        Arrays.fill(dp[1], 1); // dp[1][0]=dp[1][1]=dp[1][2]=1

        for (int i = 2; i <= n; i++) {
            // 사자가 i번째 줄에 없어도 되는 경우
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;

            // i번째 1번째 칸에 사자가 있는 경우
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;

            // i번째 줄에 2번째 칸에 사자가 있는 경우
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
        }
        System.out.println((dp[n][0] + dp[n][1] + dp[n][2]) % 9901);

    }
}