백준 1309번 - 동물원 (Java)

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

1309번: 동물원

 

코드 :

dp - bottom up

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

public class Main {

    public static final int MOD = 9901;
    public static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //dp[0][0] 크기 1의 칸에서 0번째 행에 공백일 때 경우의 수
        //dp[0][1] 크기 1의 칸에서 0번째 행에 왼쪽에 사자가 있을 떄 경우의 수
        //dp[0][2] 크기 1의 칸에서 0번째 행에 오른쪽에 사자가 있을 떄 경우의 수
        dp = new long[N][3];
        dp[0][0] = dp[0][1] = dp[0][2] = 1;

        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-1][0] +dp[N-1][1] + dp[N-1][2]) % MOD);
    }
}

 

풀이 :

탑다운 방식으로  했더니 구석구석 나눠도 자꾸 음수값이 나와서 실패했다. 우선 바텀업으로 풀었다.

 

먼저 우리가 한 행만 존재한다고 생각하면 사자가 있을 수 있는 경우의 수는 3가지이다. (없거나, 왼쪽 하나, 혹은 오른쪽 하나)

그 상태에서 한 행씩 늘리면서 경우의 수를 따져보면, 세 가지 케이스로 나뉜다.

 

1) 이전 행이 공백인 경우

- 다음 행에 3가지 경우가 다 올수 있음 

=> dp[N][0]

 

2) 이전 행의 왼쪽에 사자가 있는 경우

- 다음 행에 공백 혹은 오른쪽에 사자가 올 수 있음

=> dp[N][1]

 

3) 이전 행의 오른쪽에 사자가 있는 경우

- 다음 행에 공백 혹은 왼쪽에 사자가 올 수 있음

=> dp[N][2]

 

이차원 배열을 선언해서 행에는 인덱스를, 열에는 사자의 위치에 따라 지정한 값(공백인 경우0, 왼쪽 1, 오른쪽 2로 지정)을 넣은 것이다.

dp로 값을 기억하면서 늘리면 된다.