백준 | 11726번. 타일 채우기 - DP 문제

🟦 백준 11726번. 타일 채우기

문제

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

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

입력

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

출력

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

풀이

• 문제 분석 : 2 X N 크기의 직사각형을 1 X2 or 2 X 1 크기의 타일로 채우는 경우의 수를 구하는 문제이다.

1) D[N] = 2 X N크기의 직사각형을 타일로 채울 수 있는 경우의 수

2) D[1] = 1. D[2] = 2. D[3] = 3. D[4] = 5 … 이런 식으로 확장된다.

규칙성이 보인다. 즉. D[i] = D[i-1] + D[i-2] 이다.

3) 점화식으로 for(int i=3~N)까지 D[] 배열의 값들을 미리 도출해낸다. 이때 문제에서 각 도출한 결과에 10,007의 mod 연산을 해야한다는 사실 잊지 말것

4) 마지막에 D[N] 결과를 뽑으면 된다.

import java.util.Scanner;

/* 백준 11726번. 2Xn 타일링
 * */
public class Main {
	//MOD 는 long타입으로 선언할 것 *** RunTIme 에러 발생 안하게 
	static final long MOD = 10007;
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();//타일링
		//D long 타입 
		long [] D = new long[1001];//N의 크기는 최대 1000 이므로 : 이거 때문에 자꾸 RunTime 에러 발생 
		
		D[0]=0;
		D[1]=1;
		D[2]=2;
		
		for(int i=3; i<=N; i++) {
			D[i] = (D[i-1] + D[i-2]) % MOD;//나눈 결과값
		}		
		System.out.println(D[N]);
	}
}