[백준, BOJ 11726] 2xn 타일링 (java)

출처-https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

728x90

 

내가 푼 방식

: dp[i]는 dp[i-1]에서 2x1 타일 하나를 덧붙인 모양과 같다.

 또한 dp[i-2]에서 1x2 타일을 덧붙인 모양과 같다.

 두 경우는 겹치는 경우가 없으므로 dp[i]=dp[i-1]+dp[i-2]이다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();

		int dp[]=new int[n+1];
		dp[0]=1;
		dp[1]=1;
		for (int i=2;i<=n;i++) {
			dp[i]=dp[i-1]+dp[i-2];
			dp[i]%=10007; //int타입의 데이터 범위가 벗어나는 것을 방지
		}
		System.out.println(dp[n]);
	}

}