[baekjoon] 백준 11726번 : 2*n 타일링 (by python) 다이나믹프로그래밍

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

11726번: 2×n 타일링

 

정답 code

# 2*n 타일링
import sys
input = sys.stdin.readline
n =  int(input())
sol = [0]*n

for i in range(1,n+1):
    if i == 1:
        sol[i-1] = 1
    elif i == 2:
        sol[i-1] = 2
    else:
        sol[i-1] = sol[i-2] + sol[i-3]
    

print(sol[-1]%10007)

 

solution

2*n 직사각형에 2*1이나 1*2타일로 채워야하는데 뭔가 규칙이 있을것 같아 2*6직사각형까지 타일링을 해봤다.

결과는 역시

2*1 -> 1

2*2 -> 2

2*3 -> 3

2*4 -> 5

2*5 -> 8

2*6 -> 13

 

2*n직사각형에 타일링하는 방법의 수는 =  2*(n-1)직사각형 방법 + 2*(n-2)직사각형 방법 과 같았다. 

 

이를 단순히 프로그래밍해주면 문제는 해결된다.