[백준] 1309: 동물원 (DP) - JAVA

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

 

 

# 문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

 

# 예제

입력 :  첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

4

 

출력 :  첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

41

 

# 필요개념

우리에 가둘 때 인접한 우리에 가둘 수 없다. 만약 dp[3][0]에 가두어놨다면, dp[4][0]에는 가둘 수 없고, dp[4][1]에 가두거나 가두지 않아야 한다. 또 다른 조건은 아예 가두지 않는 경우도 경우의 수에 포함된다는 것이다. 그렇다면, 선택하지 않는 경우도 확인 할 수 있어야 한다.

 

가두지 않는 경우를 어떻게 알 수 있을지 고민을 했는데, 생각이 나지 않아 찾아보았고, 제일 첫번쨰 열을 가두지 않는 경우의 수를 담는 용도로 쓴 거를 보고 이를 활용하기로 했다.

 

dp[i][j]일 때, j가 0인 곳에는 행이 i인 곳에서는 선택하지 않을 때 경우의 수를 담는다. 선택하지 않을 때에는 이전 (i - 1)의 선택이 그다지 중요하지 않다. 전에 선택을 했던 안 했던 상관 없으므로, dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] 을 모두 더한 값을 넣어준다. 이런식으로 넣어주면 dp[N - 1][0], dp[N - 1][1], dp[N - 1][2] 에 각각의 모든 경우의 수가 들어있을 것이고 이를 모두 더해주면 된다.

 

이렇게 끝내면 틀렸습니다 라고 나온다. 모든 경우의 수는 9901로 나눈 나머지가 들어가야 하므로 점화식은 아래와 같이 작성한다.

dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;

 

# Code

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N][3];
        dp[0][0] = 1;
        dp[0][1] = 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]) % 9901;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
        }
        System.out.println((dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]) % 9901);
    }
}

 

# 결과