알고리즘 풀이 - 백준 11726(2xN 타일링, DP)

 

관련글

 

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

 

 

1. 문제

 

문제 링크는 여기를 참조

 

 

이 문제는 2x1 또는 1x2 타일로 2xn타일을 채우는 문제이다.

 

 

2. 풀이

 

이 문제는 2*n타일로 채운다는 것을 통해 좋은 힌트를 얻을 수 있다. 세로 길이가 2로 정해져 있기 때문에 세로를 채우려면 가로로 2개를 넣거나 세로로 1개를 넣으면 된다.

이 때, 가로로 2개를 채워서 넣게 되면 2*2만큼이 채워지게 되고 세로로 한 개를 채워 넣으면 2*1개가 채워진다.

여기서 DP로 풀 수 있다는 것을 알 수 있는데, 만약 2*n을 채울 수 있는 방법에서 n은 하나의 state가 되는 변수이고 더 작은 n만큼의 타일을 채운 것에서 규칙을 부여할 수 있다는 것을 알 수 있다.

위에서 적었듯이 세로를 채우려면 1개를 세로로 세우거나 2개를 가로로 눕히면 된다. 즉, 2*(n-1)에서 세로를 하나 채우거나, 2*(n-2)에서 가로를 2개 채우면 된다.

 

그래서, 현재 2*n의 타일을 채우기 위해 2*(n-1)과 2*(n-2)의 작은 문제가 반복적으로 나올 것이므로 Overlapping Subproblems의 조건이 만족되고 작은 문제의 결과값이 그대로 사용될 수 있으니 Optimal Substructure 또한 만족된다.

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 아래와 같을 것이다.
정의 : dp[n] = 2*n의 타일을 채우는 방법의 수

n 하나 만이 변수이므로 1차원의 배열을 통해 상태 저장이 가능할 것이다. 기저 상태와 점화식을 세워보자.

기저 상태는 2*1을 세로 하나로 채우거나, 2*2를 세로 2개 혹은 가로 2개로 채우는 방법이다. 따라서 아래와 같다.
기저 상태 : dp[1] = 1, dp[2] = 2

점화식은 아래와 같다.
점화식 : dp[n] = dp[n-1] + dp[n-2]

 

 

3. 코드

 

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

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int X = Integer.parseInt(br.readLine());
        System.out.println(bottomUp(X));
        
        br.close();
    }
    
    // Bottom-up 방식
    public static int bottomUp(int X){
        dp = new int[1001];
        
        // 기저 상태는 2*1 채우는 1개의 경우, 2*2 채우는 2개의 경우
        dp[1] = 1; dp[2] = 2;
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        for(int i=3; i <= X; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        return dp[X];
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        dp = new int[1001];
        
        // 기저 상태는 2*1 채우는 1개의 경우, 2*2 채우는 2개의 경우
        dp[1] = 1; dp[2] = 2;
        
        int X = Integer.parseInt(br.readLine());
        System.out.println(topDown(X));
        
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int X){
        if(dp[X] > 0) return dp[X];
        
        return dp[X] = (topDown(X-2) + topDown(X-1)) % 10007;
    }
}

 

 

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