[Java] 백준 11726번 2×n 타일링 (DP)

[Java]  백준 11726번 2×n 타일링 (DP)

□ 문 제

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

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

○ 입 력

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

○  출 력

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

[문제 링크] 백준 11726번 2×n 타일링

---

□ 문제풀이

n이 1, 2, 3, 4, 5일 때를 직접 그려보면 아래의 규칙을 가짐을 알 수 있다.

dp[n] = dp[n - 1] + dp[n - 2]

결과론적으로 2 X n 크기의 직사각형을 채울 수 있는 경우의 수는 2 X (n - 1)일 때 그릴 수 있는 모양에서 우측에 세로 하나짜리를 그린 것과 2 X (n - 2)일 때 그릴 수 있는 모양에서 우측에 가로 두 줄짜리를 넣은 경우와 같다.

 

하지만 왜 이렇게 되는 것인지 수학적인 점화식을 구해보고 싶었으나 실패했다. 다만 2 X n 크기에서 채우는 경우의 수를 단독으로 알 때는 동자순열을 통해 수학적으로 구할 수 있음을 알아냈다.

 

또 이해가 가지않는 것은 혼자 풀이할 때에는 DP 배열에 점화식의 내용을 반영하여 저장했다. 그런데 아무리 제출해도 틀렸다고 나오길래 왜 그런가 다른 분들의 풀이를 참조하니, 저장할 때도 10007을 나누고 그 나머지를 저장한다..?

일단 맞추기 위해 나 또한 그런 풀이로 바꾸었으나 이해는 가지 않는다..

참고사항

• 동자순열 https://blog.naver.com/mykepzzang/220823491974

전체 코드

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

public class Main {
	static int num;
	static long answer;
	static final int MAX = 1000;
	static long[] dp = new long [MAX + 1];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		
		dp[1] = 1;
		dp[2] = 2;
		
//		answer = bottomUp(num);
		answer = topDown(num);
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();		
	}
	
	static long bottomUp(int n) {
		if(n > 2) {
			for(int i = 3; i <= n; i++) {
				dp[i] = (dp[i - 1] + dp[i - 2]) % 10007; //왜 여기서 10007을 나눠서 저장하는거지..?
			}
			return dp[n];
		} else {
			return dp[n];
		}
	}
	
	static long topDown(int n) {
		if(n < 3) {
			return dp[n];
		} else if(dp[n] > 0) {
			return dp[n];
		}
		
		dp[n] = (topDown(n - 1) + topDown(n - 2)) % 10007;
		return dp[n];
	}
}