[백준 11727] 2xn 타일링 2

[문제 바로가기]👇

11727번: 2×n 타일링 2

 

 

풀이

 

1. 테이블 정의

dp[n] = 2*n 타일을 채우는 방법의 수

이라고 테이블을 정의한 다음 타일을 채우는 규칙을 찾았다

 

 

2. 규칙 찾기(점화식 찾기)

타일은 1x2, 2x1, 2x2 총 3가지의 종류가 있다.

 

만약 맨 마지막에 2x1 타일을 놓아서 2xn 타일을 모두 채웠다고 한다면

2x1 타일 앞에는 n-1개가 남게 된다.

 

 

이 n-1의 공간을 채우는 방법의 수는 위에서 정의한 테이블에 따르면 dp[n-1]에 저장되어 있다. 

 

그렇다면 맨 마지막에 1x2 타일을 놓아서 2xn 타일을 모두 채웠다고 한다면 이런 모양이 된다.

 

 

이 부분을 못 채우게 되는건가? 싶지만 1x2 타일을 놓았을 때 남은 공간을 놓을 수 있는 것은

1x2 타일 밖에 없기 때문에 1x2 타일은 두 개를 놓는다고 생각하면 좀 더 이해하기 쉽다.

이렇게 되면 1x2 타일 앞에는 n-2개가 남게 된다. 

 

 

이 n-2의 공간을 채우는 방법의 수는 위에서 정의한 테이블에 따르면 dp[n-2]에 저장되어 있다.

 

마지막으로 맨 마지막에 2x2 타일을 놓는다면 이런 모양이 되고 2x2 타일 앞에는 n-2개가 남게 된다.

이 경우는 위에서 구했던 1x2 타일을 놓는 것(공간을 채우기 위해서 2개 놓음)과 동일하다.

 

 

따라서 이런 규칙을 가지고 점화식을 만들어 보면

dp[n] = dp[n-1] + (dp[n-2]*2) 

맨 마지막에 2x1 타일이 오는 경우의 수(dp[n-1]) + 맨 마지막에 1x2타일, 2x2 타일이 오는 경우(dp[n-2]*2)

이렇게 만들 수 있다.

 

 

3. 초기값 설정

점화식을 만들고 나면 점화식을 사용하기 위해 필요한 초기값을 설정해야 한다.

점화식에서는 n-1값과 n-2값이 필요하고 테이블을 정의할 때 2xn타일을 채우는 방법을 dp[n]에 저장했기 때문에

시작을 n의 시작값이 1부터 한다

 

그래서 초기값을 채워보면 다음과 같다

2x1을 채우는 방법의 수 = dp[1] = 1;
2x2을 채우는 방법의 수 = dp[2] = 3; // 문제 예제 입력에 있음

 

 

4. 전체 코드

package Day_0328;

import java.io.*;

public class B11727 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// dp[n] : 2*n 타일을 채우는 방법의 수
		int[] dp = new int[N+1];
		if(N==1) {
			System.out.println(1);
			System.exit(0);
		}
		else {
			dp[1] = 1;
			dp[2] = 3;
			for(int i=3; i<=N; i++) {
				dp[i] = (dp[i-1]+(dp[i-2]*2))%10007;
			}
			System.out.println(dp[N]);
			br.close();
		}
	}
}

 

 

백준 11726 2xn 타일링 문제도 있는데 이 문제 풀 때는 엄청 고생했는데 이걸 풀고 풀어서 좀 더 쉽게 풀 수 있었다

DP는 많은 문제를 다양하게 풀어봐야 하는 것 같다는 걸 또 느꼈다