백준 11726 2xN타일링

백준 11726 2xN타일링

백준 1149 RGB거리

구현 전 생각

DP를 이용해서 해결한다 D[i] = D[i-1] +D[i-2]

---

아쉬운점

피보나치 수열의 경우 수가 굉장히 커지는것을 생각하지 못하였다. -> 따라서 저장 할 때마다 %100007를 이용해서 저장한다.

코드

package com.study37;

import java.util.Scanner;

//F(n) N 층의 건물에 칠 할 수 있는 방법의 수! 
//DFS를 이용한 해결
public class DP_apart {
	static int[] D;
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();
		D= new int[1001];
		D[0]=1;
		D[1]=2;

		
		for (int i = 2; i < N; i++) {
			D[i]=(D[i-1]+D[i-2])%10007;
		}
		System.out.println(D[N-1]%10007);
	}
	
}