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

목표:

• 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

조건:

• 1 ≤ n ≤ 1,000
• O(N**3)가능

solution 설명 :

• 세로의 값이 1일 때 경우의 수는 가로하나로 서있는 것): 1개 -> d[1]
• 세로의 값이 2일 때 1에서 온 것 한개 눕혀져 있는 가로두개: 1개 -> d[2]
  • 이건 추가되는 경우의 수를 말하는 것이다.
  • d[1]에서 가로로 서있는 것 하나 가져오기 때문에 d[2]의 값은 2 이다.
• 세로의 값이 3일 때 d[1]과 d[2]에서 가져와서 하나씩 붙이는 것이다.
• 세로의 값이 4일 때 d[3]과 d[2]에서 만들어진다.
• 계속간다.

N = int(input())
d = [0] * (N+1)

d[0] = 1
d[1] = 1

for i in range(2, N+1):
  d[i] = d[i-1] + d[i-2]

print(d[N]% 10007)

import java.util.Scanner;
public class Main {
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		int n = s.nextInt(), a=1, b=1, c;
		for(int i=1;i<n;i++) {
			c = a+b;a = b%10007;b = c%10007;
		}
		System.out.println(b);
	}
}