알고리즘 풀이 - 백준 1309(동물원, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

 

이 문제는 2*N의 우리에 사자를 배치하는 경우의 수를 찾는 문제이다.

 

 

2. 풀이

 

2*N칸의 우리가 주어지는데 한 마리도 배치하지 않는 경우 또한 1가지의 경우로 쳐야 한다.

N번째 위치에 사자를 배치한다면, 3가지의 경우가 있을 수 있다.

 

① N번째에 배치하지 않는 경우
② N번째에 좌측에만 배치하는 경우
③ N번째에 우측에만 배치하는 경우

 

①인 경우에는 N-1번째에 배치하지 않거나, 좌측에 하나 배치하거나, 우측에 하나 배치하는 경우가 있을 것이다.
②인 경우에는 N-1번째에 배치하지 않거나, 우측에 하나 배치하는 경우가 있을 것이다.
③인 경우에는 N-1번째에 배치하지 않거나, 좌측에 하나 배치하는 경우가 있을 것이다.

 

위와 같이 이전의 State에 따라 현재의 State가 결정되며 겹쳐서 작은 문제를 반복하여 사용하므로 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

따라서, DP로 해결할 수 있다. 문제의 정의를 다시 세워보자. State를 저장하는 배열을 DP[]라고 하자. State는 N번째 위치를 저장하는 부분과 배치 여부에 대한 경우 2가지로 하여 2차원으로 구성해야 한다.
정의 : DP[N][i] = N번째 위치에 사자를 배치하는 경우의 수
참고로 i = 0이라면 N번째 위치에 아예 배치하는 않는 경우를 의미한다.

 

점화식과 기저 상태를 알아보자.

점화식 :
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]

기저 상태는 N=1일 때이다. (index로는 0이라고 가정)
DP[0][0] = 1, DP[0][1] = 1, DP[0][2] = 1

 

참고로, 이 문제는 또 다른 규칙이 있다.
또 다른 규칙 : DP[N] = DP[N-2] + DP[N-1] * 2

이 다른 규칙을 설명하자면 다음과 같다.

DP[N] = 1~N번째 줄에 사자를 배치하는 경우의 수를 의미한다.

그런데 N번째 줄에 사자를 위치시키는 방법은 한 마리도 두지 않거나, 좌측에 한 마리, 우측에 한 마리를 두는 경우이다.

N번째 줄에 사자가 한 마리도 없는 경우 : N번째 줄이 없는 것과 같으니 DP[N-1]과 같다.

N번째 줄의 좌측에만 사자를 위치시키는 경우 : N-1번째의 우측에만 사자를 두거나 아예 두지 않는 2가지 방법이 있다.
N번째 줄의 우측에만 사자를 위치시키는 경우 : N-1번째의 좌측에만 사자를 두거나 아예 두지 않는 2가지 방법이 있다.

여기서, N-1번째의 좌 / 우측에 두거나 아예 안 두는 경우를 총합하면 DP[N-1]과 같다.

또, N-1번째에 아무것도 안두는 것은 N-1번째 줄이 없는 것과 같아서 DP[N-2]와 같다.

이 방식으로 위와 같은 점화식이 도출될 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static final int MOD = 9901;
    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());
        dp = new int[100001][3];
        dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 1;
        
        for(int i=2; i <= n; i++){
            dp[i][0] = ((dp[i-1][0] + dp[i-1][1])%MOD + 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;
        }
        
        bw.write(String.valueOf(((dp[n][0] + dp[n][1])%MOD + dp[n][2])%MOD));
        
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static final int MOD = 9901;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        dp = new int[100001][3];
        int n = Integer.parseInt(br.readLine());
        
        for(int i=0; i < 3; i++){
            topDown(n, i);
        }
        
        bw.write(String.valueOf(((dp[n][0] + dp[n][1])%MOD + dp[n][2])%MOD));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n, int i){
        if(n == 1) return dp[n][i] = 1; // 기저 상태
        if(dp[n][i] > 0) return dp[n][i]; // 기존의 값이 있는 경우
        
        if(i == 0){
            dp[n][i] = ((topDown(n-1, 0) + topDown(n-1, 1))%MOD + topDown(n-1, 2))%MOD;
        } else if(i==1){
            dp[n][i] = (topDown(n-1, 0) + topDown(n-1, 2))%MOD;
        } else {
            dp[n][i] = (topDown(n-1, 0) + topDown(n-1, 1))%MOD;
        }
        return dp[n][i];
    }
}

 

3) 다른 규칙을 사용 시

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());
        int dp[] = new int[n+1];
        dp[0] = 1; dp[1] = 3;
        for(int i = 2; i <= n; i++){
            dp[i] = ((dp[i-1] * 2) % 9901 + dp[i-2]) % 9901;
        }

        bw.write(String.valueOf(dp[n]));
        bw.flush();
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.