[백준] JAVA - 11726. 2×n 타일링

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

11726번: 2×n 타일링

생각

너비가 n이고 높이가 2인 직사각형을 1*2, 2*1 직사각형으로 채우는 경우의 수를 구하는 문제입니다.

 

n이 1일땐 한가지 경우, n이 2일땐 너비가1인 직사각형을 두개 놓는 방법과 너비가 2인 직사각형을 두줄로 쌓는 경우로 두가지가 있습니다.

 

제가 정의한 dp[n]은 너비가 n일때 1*2, 2*1 타일로 채우는 경우의 수입니다.

 

dp[n]일때 직사각형을 채울 수 있는 방법은 n-1 직사각형에서 너비가 1인 직사각형을 붙여서 만드는 경우와 n-2 직사각형에서 너비가 2인 직사각형을 붙여서 만드는 두가지 경우밖에 없습니다.

 

따라서 dp[n] = dp[n-1] + dp[n-2] 인 점화식이 성립됩니다.

 

Java Code

package com.java.algorithm;

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

public class BOJ_11726_2n타일링 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[1001]; // 너비가 n인 직사각형 채우는 경우의 수
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= N; i++) {
			dp[i] = dp[i-1] + dp[i-2]; // 너비i-1인(2*1블록)경우 너비i-2인(1*2블록) 경우
			dp[i] = dp[i]%10007;
		}
		System.out.println(dp[N]);
	}

}