알고리즘 풀이 - 백준 2133(타일 채우기, DP)

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 3xN 크기의 타일을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제이다.

 

 

2. 풀이

 

상단의 관련 문제 포스팅과 달리 이 문제는 3xN이라는 부분이 좀 어려운 부분이다. 3xN 타일을 기본적으로 채우는 방법은 아래와 같이 생각할 것이다.

3x2의 경우를 채우는 경우를 생각해보자.

 

 

위와 같은 3가지의 경우는 길이가 무조건 2이다.

 

이 문제는 타일을 옆으로 계속 채워나가는 방식이고 그 전체 경우의 수를 구하는 문제이기 때문에 이전에 채워진 상태인 경우에 의해 영향을 받고 그 결과를 그대로 사용할 수 있다. 즉, DP를 통해 해결할 수 있는 문제이다.

DP로 해결할 수 있으니 State의 정의를 살펴보자. 길이 N만이 변하는 State이므로 1차원의 배열로 구성할 수 있다.
정의 : DP[N] = 3xN 크기의 타일을 2x1, 1x2의 타일을 통해 채우는 경우의 수

 

위의 3가지 경우를 생각해보면, 이전의 경우는 이미 채워지고 추가적으로 가로 3x2를 채우는 경우의 수라고 볼 수 있다. 즉, 점화식을 다음과 같이 세워볼 수 있다.

점화식 : DP[N] = DP[N-2] * 3  (3x2를 채우는 경우가 3개임)

 

기저 상태는 어떨까? N의 길이가 0인 경우만 생각하면 된다. 실제로 주어지는 값은 N은 1 이상 30 미만이지만 점화식을 보면 이전 경우에 영향을 받게 해야 하는데 곱셈처리만 하므로 3x0을 채우는 경우를 단순히 1로 처리하면 된다.

기저 상태 : DP[0] = 1

 

그.런.데! 사실 3xN을 채우는 방법이 저 경우만 있는게 아니다..

이번엔 3x4를 채우는 경우에 위의 방식을 사용하지 않는 경우를 생각해보자.

 

 

위와 같은 2가지 경우가 있다. 즉, 길이가 좌측에 길이 2만큼이 아닌 4만큼을 채우는 경우도 생각해야 한다. 그래서 점화식은 다음과 같이 바뀌어야 한다!

점화식 : DP[N] = DP[N-2] * 3  + DP[N-4] * 2  (3x2를 채우는 경우가 3개, 3x4를 채우는 경우가 2개)

 

이게 끝이 아니다. 3x6을 채우는 경우, 3x8을 채우는 경우도 있다. 참고적으로 3x6은 다음과 같다.

 

 

이와 같이 2씩 늘리며 채우는 경우 또한 모두 카운트를 해야 한다. 즉, 최종 점화식은 다음과 같다

최종 점화식 : DP[N] = DP[N-2] * 3 + DP[N-4] * 2 + DP[N-6] * 2 ... 

 

이제 위 방식을 코드로 옮겨서 해결해보자

 

3. 코드

 

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

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static long[] dp;
    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 long[31];
        // 기저 상태. 3x0일 때는 1로 단순 초기화
        dp[0] = 1;
        
        // 홀수인 경우는 채우는 것이 불가하니 +2씩 수정
        for(int i=2; i <= n; i+=2){
            dp[i] = dp[i-2] * 3; // 맨 마지막 2칸을 채우는 경우는 3가지
            
            for(int j=i-4; j >= 0; j-=2){
                dp[i] += 2 * dp[j];
            }
        }
        
        bw.write(String.valueOf(dp[n]));
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static long[] dp;
    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 long[31];
        int n = Integer.parseInt(br.readLine());
        if(n % 2 == 0) {
            topDown(n);
        } else {
            dp[n] = 0; // 홀수 일 때는 채우는 방법 없음
        }
        
        
        bw.write(String.valueOf(dp[n]));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    public static long topDown(int n){
        // 기저 상태는 3x0일 때 1
        if(n == 0) return dp[0] = 1;
        
        // 이미 값이 있는 경우
        if(dp[n] > 0) return dp[n];
        
        // 마지막 2칸을 추가로 채우는 경우로 초기화
        dp[n] = topDown(n-2) * 3;
        
        // 4, 6, 8칸.. 채우는 경우 계산
        for(int i=n-4; i >= 0; i-=2){
            dp[n] += topDown(i) * 2;
        }
        return dp[n];
    }
}

 

 

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