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

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
비슷한 문제인 11726번(2xN 타일링)은 여기를 참조

 

 

1. 문제

 

문제 링크는 여기를 참조

 

이번 문제는 11726번과 비슷한데 거기에 타일이 하나 추가되었다.

2xn의 타일을 2x1, 2x2, 1x2의 타일로 채울 수 있는 경우의 수를 구하는 문제이다.

 

 

2. 풀이

 

이 문제는 DP로 풀어낼 수 있다. 이전 11726번과 같으나 2*2가 추가되어 n의 상태를 증가시켜 가며 채운다는 것만 변한 것이다.

따라서 2*n을 채우려면 다음과 같은 3가지 경우의 수가 있을 것이다.

ⅰ. 2*(n-1)에서 2*1로 세로로 하나 채우는 경우
ⅱ. 2*(n-2)에서 1*2로 가로로 두개 채우는 경우
ⅲ. 2*(n-2)에서 2*2로 하나 채우는 경우

따라서, n의 State에서 n-1, n-2 의 작은 문제가 반복되며 해당 결과값을 그대로 사용해 답을 구할 수 있으니 Overlapping Subproblems와 Optimal Substructure의 조건을 만족한다.

 

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

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

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

점화식은 아래와 같다.
점화식 : dp[n] = dp[n-1] + dp[n-2] + 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 채우는 3개의 경우
        dp[1] = 1; dp[2] = 3;
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        for(int i=3; i <= X; i++){
            dp[i] = ((dp[i-2] * 2) % 10007 + dp[i-1]) % 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 채우는 3개의 경우
        dp[1] = 1; dp[2] = 3;
        
        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)*2)%10007 + topDown(X-1)) % 10007;
    }
}

 

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