[Java] 백준 11726번 2xn 타일링

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

11726번: 2×n 타일링

그림을 그려서 문제를 이해해보면 쉽다.

N=1 일 때, 2x1의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 하나이다.

N=2 일때, 2x2의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 두 개와 2x1의 타일 두 개로 채울 수 있으므로 두 가지이다.

N=3 일 때, 2x3의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 세 개와 2x1의 타일 두 개, 2x1타일 하나씩 두 가지 경우로 채울 수 있으므로 총 세 가지이다.

 

따라서 경우의 수는 1, 2, 3, 5, 8, 13, 21, 34, 55, 89..로 증가한다.

즉 피보나치수열의 원리와 비슷하다.

 

위의 원리를 생각해보면 점화식은 dp [i]= dp [i-1]+dp [i-2] 임을 알 수 있다.

N=1일 때와 N=2일 때 경우의 수는 각각 1과 2였으므로 dp [1]=1, dp [2]=2로 초기화시켜준다.

 

처음 dp [] 배열의 크기를 int [N+1]로 설정했는데 N=1일 때 런타임 에러가 발생했다.

N의 크기는 1 <=N <=1000이므로 dp []의 크기는 안전하게 int [1001]로 수정했다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		
		int N = s.nextInt();
		
		int dp[] = new int[1001];
		
		dp[0]=0;
		dp[1]=1;
		dp[2]=2;
		
			
		for(int i=3;i<=N;i++) {
			dp[i]= (dp[i-1]+dp[i-2]) % 10007;
		}
        
		System.out.println(dp[N]);
		
	}
}