[백준OJ] 1309번 동물원

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

1309번: 동물원

---

 

풀이

2번째줄에 사자를 놓는 경우를 생각해보자

왼쪽에 놓기 위해서는, 1번째줄에 사자가 오른쪽에 있거나 1번째줄에 사자가 없어야한다.

오른쪽에 놓기 위해서는, 1번째줄에 사자가 왼쪽에 있거나 1번째줄에 사자가 없어야한다.

놓지 않기위해서는, 1번째줄에 사자가 왼쪽,오른쪽,없는 3가지 경우 모두 가능하게된다.

 

위를 일반화 하면 다음과 같다.

i번째줄의 왼쪽에 놓기위해서는 i-1번째 줄의 오른쪽에 사자가 있거나, i-1번째 줄에 사자가 없다.

i번째줄의 오른쪽에 놓기위해서는 i-1번째 줄의 왼쪽에 사자가 있거나, i-1번째 줄에 사자가 없다.

i번째줄에 사자를 놓지 않으려면, i-1번째에 왼쪽,오른쪽,없는 3가지의 경우가 모두 가능해진다.

 

위를 DP를 이용하여 3가지 경우를 모두 구한 뒤, N번째 줄에 사자가 왼쪽에 있을경우, 오른쪽에 있을경우, 없을경우의 수를 모두 더해준다.

 

시간복잡도

for문 한번만 탐색하면 되기때문에 O(N)이 된다.

 

코드

import java.util.Scanner;

public class Main {
    static int[][] dp;
    static int n;
    static final int MOD=9901;
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        dp=new int[n+1][3];//0:배치x 1:왼쪽 2:오른쪽
        dp[0][0]=1;
        dp[0][1]=dp[0][2]=0;
        for(int i=1;i<=n;i++){
            dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%MOD;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%MOD;
        }

        System.out.println((dp[n][0]+dp[n][1]+dp[n][2])%MOD);
        scanner.close();
    }
}