[알고리즘] 백준11726 2xn 타일링 - 자바

 

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

11726번: 2×n 타일링

 

 

[풀이 코드]

package dp;

import java.util.Scanner;

public class BOJ_11726_2xn타일링 {
	static int N;
	static int[] D;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		D = new int[1001];
		D[1] = 1;
		D[2] = 2;	
		
		for(int i=3; i<=N; i++) {
			D[i] = D[i-1] + D[i-2];
			D[i] %= 10007;
		}
		System.out.println(D[N]);
		
	}

}

- D [n]은 2xn을 채우는 방법의 수

- D[n]에서 맨 오른쪽을 채울 수 있는 경우는 아래 이미지에서 2x1 도형이 맨 오른쪽에 오는 경우와 1x2도형이 두 개 쌓여 맨 오른쪽에 오는 경우이다.

- 맨오른쪽에 올 수 있는 건 두 경우의 수밖에 없으며 점화식은 D [n] = D [n-1] + D [n-2]가 된다.