2XN 타일링

2XN 타일링 링크 :www.acmicpc.net/problem/11726

11726번: 2×n 타일링

DP는 규칙을 찾는게 중요한것 같아서 규칙찾는 연습도할겸 DP를 풀어보았습니다.

(사실DP가 제일 재미이써..ㅋㅋ)

2XN타일 문제는 2XN타일을 2X1타일과 1X2타일로 덮을 수 있는 가짓수를 구하는 문제입니다.

그냥 문제에서 피보나치냄새가 폴폴 나네요ㅋㅋ

근데 진짜 피보나치로 푸는 문제임 ㅋㅋㅋㅋ(갓보나치)

 

다음 문제의 규칙은 이렇습니다

 

 

 

다음과같이 n번째 갯수는 n-1과 n-2번째 갯수를 더한것이 됩니다.

이를 코드로 짠다면

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

public class NX2타일 {

	static int N;
	static int[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		arr = new int[1000];
		arr[0] = 1;
		arr[1] = 2;

		for (int i = 2; i < 1000; i++) {
			arr[i] = (arr[i - 1] + arr[i - 2])%10007;
		}

		System.out.println(arr[N-1]);
	}
}