/ BOJ

BOJ_11726_2xN타일링_JAVA

문제 : 2xN 타일링

링크 : BOJ_11726_2xN타일링

접근 방식

샘플 입출력에 살펴보면 2인경우에 정답은 2, 9인 경우에 정답은 55이다.

그 외에 값을 1부터 5까지 경우의 수를 구해보았는데,

1, 2, 3, 5, 8이다.

뭔가 익숙한 느낌에 피보나치 수열을 살짝 변형하여 나열해보았는데,

1, 2, 3, 5, 8, 13, 21, 34, 55

정확히 9번째에 55가 나타났다.

따라서 피보나치 수열에 대한 dp 이용으로 문제를 풀었다.

소스 코드

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

public class BOJ_11726_2xn타일링 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		int N = Integer.parseInt(in.readLine());

		int dp[] = new int[N];

		if(N == 1) {
			System.out.println(1);
			return;
		}

		dp[0] = 1;
		dp[1] = 2;


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

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

	}

}