백준 11726번 : 2xn 타일링 (Python)

알고리즘 풀이/백준

heheh 2021. 2. 4. 11:52

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

풀이

dp에 2x1부터 경우의 수를 입력한 뒤 입력된 수를 참고하여 다음 2xn 크기의 타일링을 계산한다.

현재 주어진 타일로 겹치지 않게 가장 작게 사각형을 채우는 방법은

①세로 타일 하나로 2x1 만들기 ②가로 타일 두개로 2x2 만들기 이다.

ex) 세로 타일 두개로 2x2를 만드는 경우는 ①의 경우에 속하므로 겹치는 경우이다.

따라서 2xn 타일링 경우의 수는 [ 2x(n-1)에 ①을 붙이는 경우 + 2x(n-2)에 ②를 붙이는 경우 ]이다.

n = int(input())

dp = [0,1,2]

for i in range(3,n+1):
    dp.append((dp[i-2] + dp[i-1])%10007)

print(dp[n])