[Algorithm] 🧱백준 11726 2xN 타일링

0. 문제

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

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

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

1. 아이디어

이전 사례 두 개를 더한 값이 현재 값과 같다는 것을 알게 됨
메모이제이션으로 TopDown하는 형태로 풀면 됨

3. 핵심 풀이

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

dp[n] = tiling(n-1) + tiling(n-2)

4. 코드

import java.util.Scanner;

public class DP_1 {
	static int dp[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new int[n+1];
		System.out.println(tiling(n));

	}
	
	static int tiling(int n) {
		if(n == 0 || n == 1) return 1;
		
		if(dp[n] > 0) return dp[n];
		
		dp[n] = tiling(n-1) + tiling(n-2);
		dp[n] %= 100007;
		
		return dp[n];
		
	}

}

5. 결과

성공~