[백준] 자바 11727 2xn 타일링 2

문제

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

아래 그림은 2×17 직사각형을 채운 한 가지 예이다.

2*17

입력

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

출력

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

---

테스트 케이스

 

입력 1

501

출력 1

4172

 

입력 2

1

출력 2

1

 

입력 3

1000

출력 3

7326

---

접근

코드 자체는 간단하지만 dp문제이므로 규칙 찾는 게 핵심인 문제인 듯합니다.

1.2*n 식에 들어갈 n을 입력받습니다.

1

일단 n이 몇이든간에, 시작은 그림과 같이 3가지 경우로 블록은 쌓이면서 시작합니다.(n이 1일 때만 제외하고)

 

2

n이 1일때랑, 2일 때의 개수를 직접 세보았습니다.

3

f(3)부터는 규칙이보이게됩니다.

첫 사진에 설명한 것처럼 3가지 경우로 시작할 수밖에 없는데, 3가지 경우로 시작한 경우 남는 블록수만큼 f(n)을 지정하여 더해주면 됩니다.

따라서 f(n) = f(n-1) + 2*f(n-2)라는 점화식이 나오게 됩니다.

이를 이용하여 코드를 짜니 문제가 해결되었습니다.

---

코드

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

public class Main {

	/*
 	 11727 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> list = new ArrayList<>();
		list.add(1);
		list.add(1);
		for(int i=2; i<=num; i++) {
			list.add((list.get(i-1) + 2*list.get(i-2))%10007);
		}
		bw.write(String.valueOf(list.get(num)));
		
		bw.flush();
		br.close();
		bw.close();
	}
}

---

주의

10007로 나눠서 출력해주는 것 주의.