boj 1309 동물원

문제 링크

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

문제 풀이

DP 문제
각 행을 돌면서 가능한 경우의 수를 저장한다.
가능한 경우의 수는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우 이렇게 3가지가 존재한다.
따라서, dp[n+1][0]은 사자가 없는 경우,dp[n+1][1]은 왼쪽, dp[n+1][2]은 오른쪽으로 생각
2차원 배열 dp[n+1][3]을 선언한다.
사자가 없는 경우는 그 전에 왼쪽,오른쪽,없는 경우가 다 가능한다.
dp[i][0]= dp[i-1][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]

전체 코드

package BOJ;

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

public class 동물원 {

    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);

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

        }

        int result =0;
        for (int i = 0; i < 3; i++) {
            result += dp[n][i];
        }
        System.out.println(result % 9901);
    }
}