[백준] 자바 11726 2 x n 타일링

문제

2 ×n 크기의 직사각형을 1 × 2, 2 ×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

테스트 케이스

 

초록색 입력 / 검은색 출력

 

---

접근

dp문제이므로 규칙을 찾으려고 노력했습니다.

 

다음과 같이 f(n) = f(n-1) +f(n-2) 규칙을 찾아내어 코드로 옮기니 성공하였습니다.

 

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 11726 problem
	*/
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> arr = new ArrayList<>();
		arr.add(1);
		arr.add(2);
		if(num>2)
		for(int i=2;i<num;i++) {
			arr.add((arr.get(i-1)+arr.get(i-2))%10007);
		}
		
		bw.write(String.valueOf(arr.get(num-1)));
		bw.flush();
		bw.close();
	}
	
}

---

주의

10007로 나누어주는 과정이 필요합니다.

또한 미리미리 10007로 나누어 저장하지 않는다면 오버플로우가 발생할 수 있습니다.