[Java] 2133 타일 채우기

문제

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

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

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

문제 풀이

DP 문제이다. 우선 3xN 칸이기 때문에 N이 홀수 일 경우는 타일을 채울 수 없어 답은 무조건 0이다.

즉, N이 짝수 일 경우만 구하면 된다.

N = 2일 경우는 3개이다.

 

N = 4 일 경우는 N=2일 경우의 수가 2개 있는 것이므로 3 * 3개의 수가 필요하고 추가로 아래와 같은 형태 2가지가 더 필요하다. 즉 3 * 3 + 2 = 11개 가 된다. 

N = 6 의 경우는 N = 4 인 경우에 N = 2 인경우를 붙이는 거로는 조금 모자라다. N=4 경우에서 발행한 2개의 모양이 N-2 경우의수 뒤에 붙는 등의 경우의 수를 놓칠 수 있다.

 

즉 이전에 나타났던 특별 타일 * 2 그 전전 타일 개수를 구해주어야한다.

N = 6의 경우에만 나타나는 특별한 경우의 수 2개는 덤이다.

 

슬슬 점화식이 보인다. dp[N] = dp[N-2] * 3 + .......... dp[N - 2i] * 2 + 2

자바 코드

import java.util.Scanner;

public class N2133 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];

	// 홀수일 경우 0반환 후 종료
        if(N % 2 == 1) {
            System.out.println(0);
            System.exit(0);
        }

	// n = 0, n = 2
        dp[0] = 0;
        dp[2] = 3;

	// n = 4인 경우의 수부터 +2씩 올려가며 구한다.
        for(int i = 4; i <= N; i += 2){
        	// 기본적으로 이전 i - 2 경우의 수 * 3 한만큼은 공통적으로 들어간다.
            dp[i] = dp[i - 2] * 3;
            
			// 이후 j를 4부터 시작하여 i가 0이 될 때 까지 i - j 한 dp값 * 2 만큼 추가로 더해준다.
            for(int j = 4; j <= i; j += 2){
                dp[i] += dp[i - j] * 2;
            }
            
	// 마지막으로 해당 N의 개수에서만 특별히 만들어지는 모양 2개를 추가한다.
            dp[i] += 2;
        }

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

 

 

참조

https://hello-backend.tistory.com/156

[백준 2133번] 타일 채우기 - java