[BOJ] 2133 - 타일 채우기 JAVA

www.acmicpc.net/problem/2133

2133번: 타일 채우기

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

 

 

 

 

풀이 1. (틀린 코드)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 0;
        for(int i = 2; i <= n; i++) {
            if(i == 2) {
                dp[i] = 3;
                continue;
            }
            if(i % 2 == 1) {
                dp[i] = 0;
                continue;
            }
            dp[i] = dp[i-2] * 3 + dp[i-4] * 2;
        }
        System.out.println(dp[n]);
    }
}

 

일단 n이 홀수인 경우는 절대로 타일을 다 채울 수 없다.

i = 2, 3 일 때는 조건문으로 따로 처리하고 4부터 반복이 제대로 돌게 했다.

i 번째로 올 수 있는 경우가 i-2, i-4 두 가지 경우만 있을 거라고 생각했는데, 이게 잘못된 생각이었다.

거의 다 온 거였는데.. 아쉽다.

 

 

 

풀이 2. (정답 코드)

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

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

 

i 번째에 도달할 수 있는 경우

1. i-2번째에서 3가지 경우 존재

2. i-4 부터 -2씩 반복하며 0이 될 때까지 2가지씩 계속 존재