[JAVA / 자바] 백준(BOJ) 11727번 - 2xn 타일링 2 (실버 3)

 문제 

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

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

---

 입력 

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

---

 출력 

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

---

 

---

 문제 접근 방법 

이번 문제는 이전 [JAVA / 자바] 백준 11726번 - 2xn 타일링 문제와 많이 동일하다.

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

 

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

n = 1 일 때, 1가지

|

n = 2 일 때, 3가지

||, =, ㅁ

n = 3 일 때, 5가지

|||, |=, =|, |ㅁ, ㅁ|

n = 4 일 때, 11가지

||||, ||=, ||ㅁ, |=|, |ㅁ|, =||, ㅁ||, ==, =ㅁ, ㅁ=, ㅁㅁ

n = 5 일 때, 21가지

|||||, |||=, |||ㅁ, ||=|, ||ㅁ|, |=||, |ㅁ||, =|||, ㅁ|||, |==, |=ㅁ, |ㅁ=, |ㅁㅁ, =|=, ㅁ|=, =|ㅁ, ㅁ|ㅁ, ==|, ㅁ=|, =ㅁ|, ㅁㅁ|

....

위 케이스를 바탕으로 점화식은

if(x가 짝수) f(x) = f(x-1)*2 + 1, else(x가 홀수) f(x) = f(x-1)*2 - 1라는 것을 알 수 있다.

그러나, 문제에서 최종 답에서 10,007로 나눈 나머지를 구하라 하였으므로, f(x) %= 10007 해준 값을 저장한다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 백준(BOJ) - 11726: 2xn 타일링문제를 풀고 난 후에 푼 문제로, 점화식이 같은 논리로 도출이 되어 바로 풀 수 있었다.

---

 문제 원본 

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

11727번: 2×n 타일링 2

 알고리즘 분류 

• 다이나믹 프로그래밍