[백준 Silver 1] 1309 동물원 - Java

문제링크 : https://www.acmicpc.net/problem/1309

1309번: 동물원

 

접근 과정 : 

• 2차원 배열(zoo[][])을 선언하고, 
• 2칸 모두 사자가 없는 경우 / 왼쪽칸에 사자가 있는 경우 / 오른쪽칸에 사자가 있는 경우로 경우의 수를 더했다
• 즉, Bottom-Up 방식으로 DP를 구현하였다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    동물원
*/

import java.io.*;

public class BOJ1309 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] zoo = new int[N + 1][3];
        zoo[1][0] = 1;
        zoo[1][1] = 1;
        zoo[1][2] = 1;


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

        System.out.println((zoo[N][0] + zoo[N][1] + zoo[N][2]) % 9901);

    }
}

 

P.S 

다른 사람의 코드를 보니,

DP[N] = DP[N-2]+(DP[N-1]*2) 라는 점화식이 성립하더라...