[백준] 11726 2×n 타일링 파이썬(Python)

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

11726번: 2×n 타일링

문제 설명

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

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

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악한 것은 '2xn개의 크기의 직사각형을 1x1,1x2로 채우는데.. n=1,n=2....의 과정 및 결과를 비교하며 규칙이 있는지 파악할 것 같은디...??'였다.

② 아이디어 열기

(1) 과정 및 결과 확인

n = 1 ; 1

n = 2 ; 2

n = 3 ; 3

n = 4 ; 5

n = 5 ; 8 

n = 6 ; 13 

n = 7 ; 21 

...            

 결과를 보고 규칙을 대충 어림짐작했다...! 바로 이건 규칙이 피보나치 아닌가???였다. 

 우연찮게도 피보나치 규칙이 맞았다--!!!

# 11726
n = int(input())

d = [0]*(n+2)
d[1] = 1
d[2] = 1

for i in range(3,n+2) :
    d[i] = d[i-1] + d[i-2]

print(d[n+1])

 사실상 피보나치 규칙이기에 꼭 dp로 안풀어도 되지만 보텀업형식의 방법으로 풀어보았다. 

 점화식 형태는 f(n) = f(n-1) + f(n-2) (n>=3) (f(1) = 1, f(2) = 1)

---

후기 

 결과에 의해 규칙이 비교적 쉽게 찾아졌다.