[DP] BOJ_2133: 타일 채우기

도저히 규칙을 찾지 못해서 고생깨나 했던 문제이다. 결국 규칙을 못 찾아서 구글링을 통해 힌트를 얻고 나서야 비슷하게 도전해 볼 수 있었다.

 

사실 DP 관련한 문제들이 다 규칙을 찾기만 하면 무난하게 풀 수 있는데, 규칙을 못 찾아서 문제가 되는 것 같다.

 

규칙은 다음과 같다.

1. n이 홀수인 경우, 타일을 채우는 경우가 존재하지 않는다.

 

2. n이 짝수인 경우, '독특하게' 타일을 채우는 방법이 2가지씩 존재한다.

 

사실 여기까지는 나 스스로도 바로 찾아낼 수 있었지만, 이 이후로 이것을 규칙화하는 데 문제가 발생하였다.

 

그리고 그 문제를 해결해 주는 키워드는 '나누어서 생각하기' , 그리고 '함수처럼 생각하기' 였다.

 

우선, 3*n size의 벽을 채우는 경우의 수를 f(n)이라고 하자. 그렇다면 가장 작은 경우인 f(2)=3이 될 것이다.

 

그 다음 n=4인 경우를 살펴보면, 이는 다음과 같이 나누어 생각해 볼 수 있다.

즉, f(4) = f(2)*f(2) + 2 이다.

 

n=6인 경우도 생각해 보자. 

 

먼저, 2칸-4칸으로 나누는 경우의 수는 f(2)*f(4) 이다.

 

그 다음으로, 4칸-2칸으로 나누는 경우의 수를 생각해 봐야 한다. 그러나 여기서 고려해야 할 것이, 일반적인 경우의 수  -즉 각 단계마다 나오는 특별한 경우- 를 제외하고는 이미 앞의 f(2)*f(4)에 포함되어 있다는 점이다.

 

예를 들어 이런 경우이다.

그래서, 4칸 - 2칸으로 나눌 때는 앞의 4칸이 4칸 고유의 경우의 수 2가지로 구성되는 경우만 생각해야 한다.

 

따라서 f(6) = f(2)*f(4)+2f(2)+2 이다.

 

결과적으로 보편적으로 적용되는 식은 f(n) = f(2)*f(n-2) + 2f(n-4) + 2f(n-6) +..... +2f(2) + 2 가 되겠다.

 

이를 바탕으로 작성한 코드는 아래와 같다.

package DP;

import java.io.*;

public class BOJ_2133_re {
    static int[] dp = new int[31];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp[2]=3;
        for(int i=1;i<n+1;i++){
            if(i%2!=0){
                dp[i]=0;
            }else if(i%2==0&&i>=4){
                dp[i] = dp[2]*dp[i-2];
                for(int j=4;j<i;j+=2){
                    dp[i]+=2*dp[i-j];
                }
                dp[i]+=2;
            }
        }

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

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

지적, 조언, 교정 언제나 환영합니다!