백준 2133번 - 타일 채우기 (Java)

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

2133번: 타일 채우기

코드 :

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

public class Main {
    static Integer[] dp= new Integer[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;
        dp[4] = 11;

        System.out.println(recur(N));
    }

    public static int recur(int N){
        if(N % 2 == 1){
            dp[N] = 0;
            return dp[N];
        }
        if(dp[N] == null){
            dp[N] = recur(N - 2) * 3 + 2;

            for (int i = 4; i < N; i+=2) {
                dp[N] += recur(N - i) * 2;
            }
        }
        return dp[N];
    }
}

풀이 :

직접 그려보면 3 * 2 짜리 모양의 도형 3가지 경우의 수와, 아래와 같은 모양의 3 * 4 짜리 도형이 나올 수 있다.

문제는 위 도형에서 아래 부분만 떼어서 볼때, 

이 부분에 1 * 2를 2개 합한 모양을 추가하면, 늘리면 3 * 4 뿐만 아니라 3 * 6, 3 * 8 ... 모양도 계속해서 만들 수 있다. 3 * 4 도형까지밖에 생각을 못해서 더럽게 많이 틀렸다.

 

참고 :

https://yabmoons.tistory.com/536

[ 백준 2133 ] 타일 채우기 (C++)

도형 모양도 해당 블로그에서 가져왔다. 상당히 상세한 설명이 있어서 감사했다.