[BOJ 1309] 동물원 (Java, DP)

 

 

---

문제 링크 

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

1309번: 동물원

---

문제 풀이 

- 시간복잡도 O(N) 

- 최대치의 경우 9907에 대한 나머지를 구하라 하므로 Integer로 예상 가능 (문제 설명에 나머지 처리 없는 경우 최대치 잘 파악) 

 

2 * 1 일때

0 의 경우 아무것도 없는 경우

1의 경우 왼쪽에 사자가 있는 경우

🦁

2의 경우 오른쪽에 사자가 있는 경우 

🦁

 

2 * 2의 경우 

1) 앞에 블록에 빈 우리 더할 경우 : 3가지

 

🦁

 

	🦁

2) 왼쪽에 사자🦁가 있는 우리를 추가하는 경우 : 2 가지

빈 우리 아래에 추가하거나

🦁

오른쪽에 사자가 있는 우리 밑에 추가 할 수 있다

	🦁
🦁

 

 

3) 오른쪽에 사자🦁가 있는 우리를 추가하는 경우 : 2 가지

마찬 가지로 빈 우리 아래에 추가하거나

	🦁

 

왼쪽에 사자가 있는 우리 밑에 추가 할 수 있다

🦁
	🦁

 

2 * N 일때

N 번째 행에서 0의 경우 이전 행의 0, 1, 2 열 다 합침

N 번째 행에서 1의 경우 이전 행의 0, 2 열 합침 ( 사자를 가로, 세로에 둘 수 없으므로 1은 안됨) 

N 번째 행에서 2의 경우 이전 행의 0, 1 열 합침 ( 사자를 가로, 세로에 둘 수 없으므로 2은 안됨) 

 

DP[N][0] = DP[N - 1][0] + DP[N - 1][1] + DP[N -1][2]
DP[N][1] = DP[N - 1][0] + DP[N - 1][2]
DP[N][2] = DP[N - 1][0] + DP[N - 1][1]       

// DP[N-1][1] 이전 우리에서 사자가 왼쪽에 있는 경우 
// DP[N-1][2] 이전 우리에서 사자가 오른쪽에 있는 경우

---

제출 코드 

1) Bottom-Up (상향식)

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;

    static int MOD = 9901;
    static int[][] A;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }

    static void pro() {
        A = new int[100001][3];
        A[0][0] = 1;
        A[1][0] = 1;
        A[1][1] = 1;
        A[1][2] = 1;

        for(int i = 2; i <= 100000; i++) {
            A[i][0] = (A[i - 1][0] + A[i - 1][1] + A[i - 1][2]) % MOD;
            A[i][1] = (A[i - 1][0] + A[i - 1][2]) % MOD;
            A[i][2] = (A[i - 1][0] + A[i - 1][1]) % MOD;
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();

        int result = 0;
        for(int v : A[N]) {
            result += v;
            result %= MOD;
        }

        System.out.println(result);
    }
    
}

 

2) Top-Down (하향식) 

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;

    static int MOD = 9901;

    static int[][] DP;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        DP = new int[N + 1][3];
        int result = (topDown(N, 0) + topDown(N , 1) + topDown(N , 2)) % MOD;

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();

        br.close();
    }

    static int topDown(int height, int cageNumber) {
        if(height == 1) return 1;

        if(DP[height][cageNumber] == 0) {
            if(cageNumber == 0) {
                DP[height][cageNumber] = (topDown(height - 1, 0) + topDown(height - 1, 1) + topDown(height - 1, 2)) % MOD;
            } else if(cageNumber == 1) {
                DP[height][cageNumber] = (topDown(height - 1, 0) + topDown(height - 1, 2)) % MOD;
            } else {
                DP[height][cageNumber] = (topDown(height - 1, 0) + topDown(height - 1, 1)) % MOD;
            }
        }

        return DP[height][cageNumber];
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}

 

3) 점화식을 사용하는 경우 

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;

    static int MOD = 9901;
    static int[] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }

    static void pro() {
        DP = new int[100001];
        DP[0] = 1;
        DP[1] = 3;

        for(int i = 2; i <= 100000; i++) {
            DP[i] = (2 * DP[i - 1] + DP[i - 2]) % MOD;
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
        System.out.println(DP[N]);
    }
    
}

 

손으로 그려서 점화식을 구하긴 했었는데, 증명이 되지 않았다 (아래 참고)

https://www.acmicpc.net/board/view/10263

글 읽기 - 1309 동물원 점화식 질문 드립니다.

 

내가 해석한 증명 

DP[1] = 1 의 경우 아무것도 없어도 1이라는 지문에 따름

 

DP[2] = 3의 경우 아래와 같은 3가지 경우가 나옴

 

🦁

 

🦁

 

백준 질문/답변에 내용을 해석해보자면 

DP[3] = 7 일때

1) 

? ?

X X  아무것도 없는 빈 우리를 붙이는 경우는 DP[N - 1] 수와 같다 (3가지)

 

2)

그리고 왼쪽에 사자가 있는 우리나 오른쪽에 사자가 있는 우리를 붙이는 경우는 2 * DP[N - 1]와 같다

총 6가지가 구해지고 이때 배치하면 안되는 조합이 포함되어 있다

 

?  ?

🦁 X

 

? ?

X 🦁

 

3)

가로, 세로 같은 위치에 🦁 있는 경우가 2)에 포함되어 있어서 제거해야 함

DP[N - 1] - DP[N - 2] 뜻하는게 보면 DP[2] 에서 빈 우리만 (DP[1])빼면 원하는 중복 경우가 2가지 확인 가능

 

🦁 X

🦁 X

 

X 🦁

X 🦁

 

그래서 점화식을 구하면 

DP[N - 1] + 2 * DP[N - 1] - (DP[N - 1] - DP[N - 2]) = 2 * DP[N - 1] + DP[N - 2] 가 구해지는 거였다.

- DP[N - 1] : 아무것도 없는 빈 우리를 붙이는 경우

- 2 * DP[N - 1] - (DP[N - 1] - DP[N - 2]) : 🦁 X 또는 X 🦁 우리를 붙일 때 예외 케이스 제거

 

다시 풀어서 보면

- DP[0] : XX

- DP[1] : XX , 🦁 X, X 🦁  

- DP[2] 를 구할 때 DP[1]에 X X를 붙이는 DP[N - 1] 경우 3가지와 🦁 X, X 🦁 를 붙이는 2 * DP[N - 1]의 경우에서 예외 케이스를 제거하면 값이 구해진다(DP[1] - DP[0] = 🦁 X, X 🦁 )