[백준 1309번] 동물원 - JAVA

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

1309번: 동물원

풀이

사용한 알고리즘 : DP(Dynamic Programming)

 

풀이전략

N=1일 때, 동물원에서 우리의 형태는 아래와 같다.

첫 행에 사자가 있을 경우는

(1) 없는 경우 ( =d[1][0])

(2) 1열에 하나 있는 경우 ( =d[1][1])

(3) 2열에 하나 있는 경우 ( =d[1][2])

로 총 3가지 경우가 있다.

 

N=2일 때, 동물원에서 우리의 형태는 아래와 같다.

두번째 행에서 사자가 있을 경우는

(1) 사자가 없는 경우

: 첫번째 행에서 사자가 어떤 형태로 있어도 상관없다.

d[2][0] = d[1][0]+d[1][1]+d[1][2]

 

(2) 1열에 사자 한 마리가 있는 경우

: 첫번째 행에서 사자가 없거나 2열에 있는 경우에만 가능하다.

d[2][1] = d[1][0]+d[1][2]

 

(3) 2열에 사자 한 마리가 있는 경우

: 첫번째 행에서 사자가 없거나 1열에 있는 경우에만 가능하다.

d[2][2] = d[1][0]+d[1][1]

 

따라서 위 방식으로 메모이제이션을 실행하면 우리가 원하는 수까지의 사자 배치 경우의 수를 구할 수 있다.

 

제출코드

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N =Integer.parseInt(br.readLine());

        long d[][]=new long[N+1][3];
        d[1][0]=1;
        d[1][1]=1;
        d[1][2]=1;
        for(int i=2;i<=N;++i){
            d[i][0]=(d[i-1][0]+d[i-1][1]+d[i-1][2])%9901;
            d[i][1]=(d[i-1][0]+d[i-1][2])%9901;
            d[i][2]=(d[i-1][0]+d[i-1][1])%9901;
        }

        long answer=(d[N][0]+d[N][1]+d[N][2])%(long)9901;
        bw.write(answer+"\n");
        bw.flush();
        bw.close();
    }
}