BOJ G4 2133 타일 채우기 JAVA

2133번: 타일 채우기

 

---

 

문제 읽기

 

우선 문제 자체는 매우 짧고 예전에 싸피 수업 때 본 듯한 문제였다. 이런 문제는 직접!! 그려봐야 규칙이 보인다.

 

---

 

문제 풀기

우선 3xN의 크기의 판에 2x1, 1x2 크기의 타일을 남김없이 붙여 채워야 한다. 나는 규칙을 찾기 위해 N의 범위만큼 다 그려보았다. (N : 1~30)

 

N = 0, 1

어차피 DP 배열은 0도 있을 거니까 그냥 그렸다

N이 0, 1일 때는 내가 가진 타일로 채울 수 없었다.

 

N = 2

N = 2일 때는 위와 같은 방식으로 채울 수 있었다. 문제에서 주어진 답처럼 3가지 경우가 나왔다.

 

N = 3

N = 3일 때를 그려보니 확실히 N이 홀수일 때는 절대 채울 수 없다는 걸 알았고, 짝수일 때만 고려하기로 결정했다.

N = 4

N = 4일 때는 4를 반동강 내면 N = 2인 타일이 두 개 붙어있는 꼴이 된다. 따라서 그 경우 3*3으로 9가지 경우가 나온다.

 

 

여기서 고려할 점은 문제에서 주어진 힌트이다.

문제에서는 위와 같은 힌트를 주고 있으며, 이 힌트에서 N = 4인 경우 특이한 모양을 볼 수 있음을 알 수 있다.

따라서 이런 두 가지 모양이 더 나오기 때문에, N = 4일 경우 9 + 2 = 11가지 경우의 수가 존재한다.

N = 6

6의 경우에도 유사하게 (4, 2), (2, 4) 형태로 나누어볼 수 있고, 이 경우에는 다음과 같은 경우의 수가 나온다.

(4, 2) ⇒ DP[4] * 3(=DP[2]) = 33

(2, 4) ⇒ DP[2] * 2(N = 4일 때 특이한 모양들) = 6

 

또한 N = 6일 때도 다음과 같이 특이한 모양이 존재한다.

따라서 +2를 해주면 총 41가지 경우의 수를 볼 수 있다.

 

이처럼 N = 8, 10, 12… 쭉 하다 보면 위와 유사한 방식으로 기존의 값을 이용하고, 특이한 모양 2개가 각각 생겨나게 된다. 이를 이용하여 점화식을 다음과 같이 세워볼 수 있다.

 

점화식

DP[n] = DP[n-2]* 3 + DP[n-4] * 2 + DP[n-6] * 2 + … + DP[0] * 2 (DP[0] = 1)

 

밑줄 친 부분이 기존의 값을 이용하는 모양이고, 진하게 표시한 부분이 새로 생기는 특이한 모양을 나타낸다. 이러한 점화식을 이용하면 다음과 같은 코드를 작성할 수 있다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_2133_타일채우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(in.readLine());
        int[] dp = new int[N+1];

        dp[0] = 1;
        for (int i = 2; i <= N; i+=2){ //짝수만 유효함
            for (int diff = 2;; diff+=2){
                if (i - diff < 0) break;

//                System.out.println(i + ": " + (i - diff));
                if (diff == 2) dp[i] += dp[i-diff] * 3;
                else dp[i] += dp[i-diff] * 2;
            }
        }
//        System.out.println(Arrays.toString(dp));
        System.out.println(dp[N]);
    }
}

---

실수한 부분

사실 처음부터 점화식을 완벽하게 파악하진 못했고, 문제를 여러 번 제출하면서 완전히 알았던 것 같다. 점화식 세우는 걸 많이 연습해야 할 것 같다.

또 DP[0]에 대해서 처음에는 그냥 0으로 두었었는데, 점화식을 세우고 다시 한 번 점검해야겠다고 다짐했다.