문제 이해

2 * n 직사각형을 1*2, 2*1 타일로만 채우는 방법의 수를 구하는 문제이다.

---

문제 풀이

DP 점화식을 구하기 위한 가장 핵심적인 방법은 나는 아래와 같다 생각한다.

"현재 상황에서 어떻게 하면 문제 제한 조건을 모두 활용하며 과거의 데이터를 사용할 수 있을 것인가"

이 문제를 위 문장에 대응해서 바꿔보자

"2*n 타일링을 채우고 싶은데, 1*2 혹은 2*1 직사각형만 사용할 수 있다. 2*(n-1), 2*(n-2), ... 타일 채우는 방법의 수는 모두 알고 있고, 이를 활용하고 싶다"

2*(n-2)타일링에서 1*2 타일링 2개를 사용하면 2*n타일링을 만들 수 있다.
또한 2*(n-1) 타일링에서 2*1 타일링 1개를 사용하면 2*n타일링을 만들 수 있다.
위 경우의 수가 제한 조건인 직사각형 타일을 최소한으로 사용하는 유이한 방법이다.

따라서, 점화식은 아래와 같을 것이다.

$DP\left(n\right)\ =\ DP\left(n-1\right)\ +\ DP\left(n-2\right)$

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] answer = new int[1001];
	
	static void dp(int T) {
		answer[1] = 1;
		answer[2] = 2;
		for(int i=3;i<=T;i++) {
			answer[i] = (answer[i-1]+answer[i-2])%10007;
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();

		dp(T);
		
		System.out.println(answer[T]);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 : 문제에서는 방법의 수를 "10007로 나눈 나머지"를 구하고 싶다. 하지만 10007로 나누는 과정을 수행하지 않아 틀렸다.