백준 11726 2xN 타일링 (Java)

1. 문제 링크

11726번: 2×n 타일링

 

2. 문제 및 입출력예제

 

3. 문제 풀이

하나씩 그려보면 a[i] = a[i-1] + a[i-2] 라는 점화식이 나온다는 것을 알 수 있다.

그려보면 간단하게 알 수 있다.

 

문제를 읽어보면 10007로 나눈 나머지를 출력하라고 하는데 마지막 결과에서만 나눠서 답이 나오지는 않는다.

앞선 배열의 값을 이용하기 때문에 모든 값을 저장하기 전에 나누는 과정이 필요하다.

 

그리고 1이 들어간 경우나 2가 들어간 경우도 생각해야 된다.

 

4. 코드

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

public class Main {
	private static StringBuilder sb = new StringBuilder();
	private static int[] arr;

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