[BaekJoon] 2133번 타일 채우기 (Java) 문제 풀이 [Gold 4]

문제

https://www.acmicpc.net/problem/2133

 

어떻게 풀 것인가?

처음 문제를 풀었을 때 우선적으로는 DP가 떠올랐다.

DP 정리는 아래에 있다.

https://superohinsung.tistory.com/198

[Algorithm] 동적 계획법(Dynamic Programming)

 

세로 3칸의 크기는 고정되었다. 즉, 주어지는 N에 따라서 타일을 채울 수 있는 경우의 수가 달라진다.

그래서 간단하게도 이 문제는 N 1 ~ 4까지의 경우의 수를 찾으면 문제의 점화식이 보인다.

 

N = 0일 경우

타일이 없을 경우 2x1, or 1x2의 타일로 채울 수 있는 경우의 수는 아무것도 채우지 않는 경우이다

 

N = 1일 경우

3 x 1 타일을 채울 수 있는 경우의 수는 0개이다.

 

N = 2 일 경우

3 x 2 타일을 채울 수 있는 경우의 수는 3개이다.

 

위와 같이 우선적으로 짝수인 경우와 홀수인 경우가 다르니 한번 짝수를 토대로 경우의 수를 찾아보자.

 

N = 4일 경우

3x4의 벽을 생각해보면 3x2의 벽을 두번 채우는 형태로 생각해볼 수 있다. 우리는 DP[2] = 3인 결과 값을 이미 알고 있다.
위의 3가지 형태를 조합해서 나타낼 경우 다음과 같이 9개의 경우의 수가 나온다.

이외에도 나눠지는 경우가 2가지 존재한다.

여기서부터 4 이전과는 다른 패턴이 보인다.

 

N = 6일 경우

3x6의 벽을 나눌 수 있는 방법은 (3x2) x (3x4)의 경우의 수와 (3x4) x (3x2)의 경우의 수가 있을 것이다. 위와 같이 계산을 수행할 경우 33개 + 33개로 66개가 나올 것이다.

 

하지만 계산하다보면 중복되는 경우의 수가 많이 존재하기 때문에 정답이 될 수 없다.중복을 제거하기 위해서는 두번째 경우의 DP[4]에 DP[2]의 경우가 들어가면 안될 것이다. 따라서 두번째 DP[4]에는 규칙이 있지 않은 패턴을 넣어주어야 할 것이다.

 

DP[4] DP[2]가 33가지의 경우의 수이고 DP[2] 2가 6가지 경우의 수를 가질 것이다. 여기서 또한 3x4에서와 마찬가지로 특별한 모양을 갖는 경우의 수가 2가지 있기때문에 2를 더해야한다.

 

자 이제 규칙성이 보인다 이를 식으로 한번 찾아보자.

DP[6] = (DP[4] x DP[2]) + (DP[2] x 2) + (DP[0] x 2)

대강 점화식이 나왔다. 이를 아래 코드로 작성해보자.

 

풀면서 놓쳤던점

생각보다 점화식을 찾아가는 과정이 오래걸리는 문제였다.

 

이 문제를 통해 얻어갈 것

DP에 대한 접근

 

내 코드 

import java.util.*;
import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[31];
        arr[0] = 1;
        arr[2] = 3;
        for (int i = 4; i < 31; i++) {
            arr[i] = arr[i - 2] * arr[2];
            for (int j = 4; j <= i; j++) {
                arr[i] += arr[i - j] * 2;
                j++;
            }
            i++;
        }
        System.out.println(arr[N]);
    }

}

 

참고

https://velog.io/@newtownboy/JAVA2133%EB%B2%88-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0

[JAVA/2133번] 타일 채우기