[백준] 타일 채우기 2133 - DP

1. 문제

 

 

2. 접근

우선 그려봤다. N이 2일 때, 4일 때, 6일 때

그려보니 4일 때 새로운 경우가 2가지 나오는 것을 알았다. 이것을 제외하면 dp[i-2]*3을 해주면 되는데, 새로운 경우를 어떻게 처리할지 몰랐다. 

 

근데 N이 4일 때 말고도 6, 8... 이 될 때마다 새로운 경우가 아래 처럼 2가지 추가됐다.

이 경우를 따로 구해줘야 한다.

dp[0] = 1;
dp[2] = 3;
for(int i=4; i<=N; i+=2){
    dp[i] = dp[i-2]*3;
    // 4부터 특별 경우가 2가지 씩 나온다
    // 근데 특별 경우가 2 단위로 계속 2개씩 추가된다.
    // 그래서 j를 빼서 현재 경우에 j블록을 넣는 경우를 생각한다
    // 구성된 4블록에서 4블록을 넣기, 구성된 2블록에서 6블록을 넣기...
    for(int j=i-4; j>=0; j-=2){
        dp[i] += dp[j]*2;
    }
}

 

만약 내가 구하는 것이 dp[6]이라할 때, 우선 dp[4]에서 3을 곱한다. 왜 3을 곱하냐면 dp[2]가(3x2), 즉 3x2를 구성하는 경우의 수가 3이기 때문이다. 그래서 3x4를 이루는 블록에 3x2 블록을 붙여주는 것이다.

이제 새로운 경우를 더해야한다. dp[2]*2를 해준다. 이건 무엇을 의미하나면, 3x2 블록에 새로운 경우의 3x4 케이스를 붙이겠다는 것이다. 즉 새로운 도형을 활용하는 경우의 수를 구한다.

이는 N이 2씩 추가될 때마다 새로운 경우가 생기니 2씩 빼주면서 더해준다.

 

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {

        int N = Integer.parseInt(br.readLine());

        long dp [] = new long[N+1];

        if(N % 2 != 0){
            System.out.println("0");
            return;
        }

        dp[0] = 1;
        dp[2] = 3;
        for(int i=4; i<=N; i+=2){
            dp[i] = dp[i-2]*3;
            // 4부터 특별 경우가 2가지 씩 나온다
            // 근데 특별 경우가 2 단위로 계속 2개씩 추가된다.
            // 그래서 j를 빼서 현재 경우에 j블록을 넣는 경우를 생각한다
            // 구성된 4블록에서 4블록을 넣기, 구성된 2블록에서 6블록을 넣기...
            for(int j=i-4; j>=0; j-=2){
                dp[i] += dp[j]*2;
            }
        }

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

 

 

 

4. 회고

이런 문제는 그려보지 않고는 못푸는 건가? N이 6일 때까지를 그려봐야 새로운 경우가 매번 2개씩 생긴다는 것을 알 수 있는데, 이게 맞나