백준 1309번 동물원 (JAVA)

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

1309번: 동물원

 

저는 DP를 적용하여 문제를 해결하였습니다. 

0번째 인덱스는 해당 라인에 사자를 넣지 않는 것으로 설정하였습니다. 해당 라인에 아무것도 없다면 이전 인덱스의 1,2 둘 다 가능하기 때문에 dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] 으로 점화식을 만들었습니다.

해당 라인에 왼쪽 (1)에 사자를 넣으면 이전 인덱스에서 2만 넣을 수 있기 때문에 점화식
dp[n][1] = dp[n-1][0] + dp[n-1][2] 으로 만들었습니다.

오른쪽(2) 도 위와 같은 방식으로 점화식을 만들면

dp[n][2] = dp[n-1][0] + dp[n-1][1]입니다. 

저는 이렇게 점화식을 만들어서 DP를 적용하여 문제 해결 하였습니다.

 

 

 

package BOJ;

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

public class BOJ_1309 {
    static int dp[][];
    static int n;
    static final int LIMIT = 9901;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n+5][3];
        dp[1][0] = 1;
        dp[1][1] = 1;
        dp[1][2] = 1;
        for(int i = 2 ;i <= n; i++){
            dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % LIMIT;
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % LIMIT;
            dp[i][2] = (dp[i-1][0] + dp[i-1][2]) % LIMIT;
        }
        int result = (dp[n][0] + dp[n][1] + dp[n][2]) % LIMIT;
        System.out.println(result);
    }
}