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

 

백준 저지에서 타일채우기를 자바를 통해 풀어 보았다. 

 

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

2133번: 타일 채우기

 

2133번 타일 채우기.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

2133번 타일 채우기

문제

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

설명

비슷한데 더 높은 티어의 문제를 풀어본 경험이 있어서 쉽게 풀 줄 알았는데 더 어려웠던거 같다.

 

일단 DP문제이다. 타일 모양만 보고 본능적으로 느껴버렸다. DP문제이니 점화식을 찾아야한다. 

 

우선 N이 홀수일 때는 어떠한 방법으로도 벽을 채울 수 없다. N이 홀수면 벽의 크기도 홀수가 나오는데 사용할 수 있는 타일의 크기는 모두 2로 짝수이다. 짝수로는 홀수 크기의 벽을 채울 수 없다.

 

N=2일 때 경우의 수는 3이다. 각각 다음과 같은 모양이다.

만약 N=k-2일 때 경우의 수가 dp[k-2]라면 N=k일 때는 dp[k-2]와 위에 있는 3가지 경우가 합쳐져 dp[k-2]*3개의 경우의 수가 생긴다.

 

N=4부터는 다음과 같이 1X2타일이 맨 위 혹은 맨 아래에 쭉 깔리고 양쪽에 2X1타일 하나씩과 중간에 1X2로 채워지는 모양이 2개가 생긴다. 이를 문 모양이라고 하자.

이런 식으로 벽을 채우는 문모양이 4 이상 짝수마다 2개씩 존재한다. 위에서는 dp[k] 다음에 바로 2개 짜리 벽이 오는 경우만 생각했지만 그 사이를 저런 문모양이 채우는 경우까지 고려해야한다.

이러한 경우는 k-4부터 2까지 각각 두개 존재하며 이 숫자를 j라고 할때 경우의 수는 dp[j]*2이다. 

 

마지막으로 N=k일 때 문모양으로 채우는 경우의 수 또한 2개 존재하므로 추가해준다.

코드

//2133번 타일 채우기.java
package week6;

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

public class 타일_채우기_2133 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[31];
		
		dp[0]=1;
		dp[2]=3;
		dp[4]=11;
		for(int n=6;n<=30;n+=2) {
			dp[n] += dp[n-2]*3;
			for(int j=n-4;j>=0;j-=2) {
				dp[n]+=dp[j]*2;
			}
			
		}
		System.out.println(dp[N]);
	}
}