[백준] [11726] 2×n 타일링 (dp) (JAVA)

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

11726번: 2×n 타일링

---

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

---

※ JAVA 코드 (2×n 타일링)

import java.io.*;

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

---

※ 생각정리 (2×n 타일링)

dp(다이나믹 프로그래밍) 문제는 대부분 코드는 간단하지만 생각을 해서 패턴을 찾아내는 문제들이다.

 

 

패턴을 찾기 위해 다음과 같이 그림을 그려가며 문제에 접근하였다.

dp[n] = dp[n-2] + (1x2 타일링) + dp[n-1] + (2x1 타일링)의 패턴이 존재한다.

예를 들어 2 x 5 크기 타일을 채우려면 2 x 4 타일을 채웠던 경우의수에 2 x 3 타일을 채웠던 경우의 수를 더하면 된다. 수식은 dp[n] = dp[n-2] + dp[n-1]

하지만 다음과 같은 패턴으로 문제에서 주어진 범위 1000까지 가면 그 수가 너무 커지기 때문에 중간에 10007로 나눈 나머지를 배열에 담으면서 반복문을 진행해 나가야한다.

-새벽코딩-