[백준] 2133번 타일 채우기

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 첫째 줄에 N이 주어지며 제한 사항은 다음과 같다.

 

• 1 ≤ N ≤ 30

 

 

---

접근 방식

   재귀의 개념을 이용한 방식과 DP의 개념을 이용한 방식 두 가지로 해결하였다.

 

<재귀 방식>

 

   이 문제의 경우 나타날 수 있는 패턴이 정해져있다. (홀수 열의 경우 모든 칸을 채우는 것이 불가능하기 때문에 제외한다.) 먼저 2열을 가지고 만들 수 있는 경우는 다음 3가지이다.

 

 

   이후부턴 길이만 늘어나며 형태는 거의 같은 패턴이 반복되며 2가지씩만 존재한다.

 

4열 패턴

6열 패턴

 

   이제 재귀 내에서 내가 사용할 패턴을 정하고 패턴에 따라 남은 열 수와 만들어질 수 있는 경우의 수를 다음 재귀로 넘겨주면 된다. 재귀는 남은 열 수가 0이하가 되는 경우에 종료되며 0으로 끝난 경우만 만들어진 경우의 수를 저장하고 최종적으로 저장된 경우의 수를 출력하면 된다. 즉, 다음과 같은 순서로 진행된다.

 

 

   최종적으로 N이 6일 때, 27 + 6 + 6 + 2 = 41의 값이 출력된다.

 

<DP 방식>

 

   DP 방식에서도 나올 수 있는 패턴의 형태는 같다. 재귀와 다른 점은 반복문을 이용해 문제를 해결한다는 것이다. 점화식을 세우기 위해 현재 인덱스(1~N 중 하나)의 값을 구하는 방법을 생각해보자. 우리가 알고 있는 정보는 N이 짝수인 경우만 칸을 다 채워 유효한 결과가 나온다는 것과 2열은 3가지, 4열, 6열, 8열 ... 등은 2가지의 패턴을 가진다는 것이다. 그렇다면 다음과 같은 점화식을 하나 세울 수 있다.

 

• dp[curIndex] = dp[curIndex - 2] * 3

 

   위의 점화식은 2열짜리 패턴을 선택하며 현재 인덱스의 값을 구하는 형태이다. 즉, 지금까지 어떤 패턴들을 선택하여 만들었는지는 모르지만 지금 당장은 2열짜리 패턴을 선택한다는 의미이다.

 

 

   하지만 이런 방식은 누락되는 경우의 수가 존재한다. 위의 점화식만을 이용하는 경우 N이 6일 때 35라는 잘못된 결과가 출력된다. 위의 그림을 통해 생각해보면 i에 도착할 수 있는 경우는 i - 2에서 2열 패턴을 선택하는 방법도 있지만 i - 4에서 4열 패턴하는 방법도 있다.

 

 

   물론 크기만 된다면 6열, 8열 패턴의 경우도 가능할 것이다. 따라서 점화식은 2열 패턴을 사용하는 경우와 2열이 아닌 짝수열 패턴을 사용하는 두 가지 경우가 생기게 된다.

---

코드

<재귀를 이용한 방법>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준2133번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int count, max;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        count = 0;
        //2열을 하나의 줄로 취급한 개수(ex 4열이면 max=2)
        max = N / 2;

        if (N % 2 == 0)
            recursive(N / 2, 1);

        System.out.println(count);
    }

    public static void recursive(int select, int total) {
        //줄을 전부 사용한 경우
        if (select <= 0) {
            //줄을 맞게 채운 경우
            if (select == 0)
                count += total;
            return;
        }
        //줄의 개수만큼 반복
        for (int i = 1; i <= max; i++)
            //select - i : 소모된 후 남은 줄의 개수
            //total * (i == 1 ? 3 : 2) : 소모한 줄로 만들 수 있는 경우의 수
            //1줄(6칸)의 경우 3가지 패턴, 이후부턴 2가지 패턴만이 존재 (접근 방식에서 확인)
            recursive(select - i, total * (i == 1 ? 3 : 2));
    }
}

 

<DP를 이용한 방법>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준2133번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        //0번째 인덱스는 dp 과정에서 참조하기위한 공간으로 사용
        int[] dp = new int[N + 1];

        if (N % 2 == 0) {
            //재귀 방식에서 total을 1로 넘겨준 이유와 동일
            dp[0] = 1;
            dp[1] = 0;
            dp[2] = 3;
            //현재 인덱스의 값은 2 이전의 인덱스의 경우 * 2열로 만들 수 있는 패턴 수와
            //2가 아닌 짝수 이전의 인덱스의 경우 * 2가 아닌 짝수 열로 만들 수 있는 패턴 수
            //를 합한 값
            for (int i = 4; i <= N; i += 2) {
                dp[i] = dp[i - 2] * 3;
                for (int j = i - 4; j >= 0; j -= 2)
                    dp[i] += dp[j] * 2;
            }
        }

        System.out.println(dp[N]);
    }
}