백준_11726 2xn타일링(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

DP를 이용한 풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Back_11726 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] D = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			if(i==1) {
				D[i]=1;
			}
			else if(i==2) {
				D[i]=2;
			}
			else {				
				D[i] = (D[i-2]+D[i-1])%10007;
			}
		}
		
		System.out.println(D[N]);
	}

}

 

이 문제의 패턴을 보면 피보나치 처럼 수가 증가하는 것을 찾을 수 있다. 따라서 DP의 해결 법은 피보나치의 기본 원리를 이용하면 쉽게풀 수 있다.