[백준 1309] 동물원

 

백준 문제중 스티커를 먼저 푼 적이 있는데, 그 문제와 유사하다.

 

사자는 가로 혹은 세로로 연속된 우리에 놓을 수 없기 때문에

우리에 놓을 때 이전 우리의 상태를 파악해야 한다.

 

우리의 상태는 0(사자가 없음), 1(좌측에 사자를 둠), 2(우측에 사자를 둠) 으로 구분했다.

0 일때 1, 2 에

1 일때 0, 2 에

2 일때 0, 1 에 사자를 배치할 수 있다.

 

탑다운 방식으로 짰다.

public static int lion(int n, int status) {
    if(n == N) return 1;
    if(dp[n][status] != -1) return dp[n][status];
        
    int ret = lion(n+1, 0) % 9901;
    if(status != 1) ret += lion(n+1, 1) % 9901;
    if(status != 2) ret += lion(n+1, 2) % 9901;
    dp[n][status] = ret;
    return ret;
}

입력으로 받은 변수 N과 재귀함수의 변수 n이 같아지면 정지하게 했다.

(A+B)%M = (A%M + B%M)%M 을 이용하여 덧셈 연산이 있을때마다 퍼센트 연산을 해줬다.

 

public class Main {
    
    static int N;
    static int dp[][] = new int[100001][3];
    
    /* status
     * 0 : 이전 배열에 배치 안함
     * 1 : 이전 배열 좌측에 배치
     * 2 : 이전 배열 우측에 배치
     */
    public static int lion(int n, int status) {
        if(n == N) return 1;
        if(dp[n][status] != -1) return dp[n][status];
        
        int ret = lion(n+1, 0) % 9901;
        if(status != 1) ret += lion(n+1, 1) % 9901;
        if(status != 2) ret += lion(n+1, 2) % 9901;
        dp[n][status] = ret;
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        
        for(int i=0; i<=N; i++)
            for(int j=0; j<3; j++)
                dp[i][j] = -1;
        
        System.out.println(lion(0, 0) % 9901);
    }
}