[JAVA / 자바] 백준 11726번 - 2xn 타일링

 문제 

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

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

---

 입력 

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

---

 출력 

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

---

 

---

 문제 접근 방법 

이번 문제는 단순히 케이스 몇 개만 따져주면 금방 점화식을 구할 수 있다.

n = 1 일 때, 1가지

|

n = 2 일 때, 2가지

||, =

n = 3 일 때, 3가지

|||, |=, =|

n = 4 일 때, 5가지

||||, ||=, |=|, =||, ==

n = 5 일 때, 8가지

|||||, |||=, ||=|, |=||, =|||, |==, =|=, ==|

....

위 케이스를 바탕으로 점화식은 f(x) = f(x-1) + f(x-2)라는 것을 알 수 있다.

그러나, 문제에서 최종 답에서 10,007로 나눈 나머지를 구하라 하였으므로, f(x) = (f(x-1) + f(x-2)) % 10007로 작성해주면 된다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 패턴을 찾으면 다이나믹 프로그래밍(Dynamic Programming)으로 어떻게 풀어야 할지 바로 감이 왔던 문제였던 것 같다. 항상 다이나믹 프로그래밍의 코드를 작성할 때 점화식을 만들기가 제일 힘든 것 같다.

---

 문제 원본 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 알고리즘 분류 

• 다이나믹 프로그래밍 (Dynamic Programming) - 추후 포스팅 예정