[백준] 11727번 (2xn 타일링 2)

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

11727번: 2×n 타일링 2

---

1. 아이디어

- n=3 ~ n=4 까지 직접 그려보며 점화식 구하기

• 점화식 : F(n) = F(n-1) + 2*F(n-2)
• N값 구하기 위해, for 문 3 부터 N 까지 값 구해서 dp 배열에 저장.
• 이전 값, 이전이전 값 더한 후, 10007로 나눈 나머지 저장.

---

2. 코드

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[1001];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 3;
		
		for(int i=3; i<=n; i++) {
			dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007;
		}
		
		bw.write(dp[n] + "");
		
		br.close();
		
		bw.flush();
		bw.close();
	}
}