[파이썬/Python] 백준 11727번 2×n 타일링 2

[파이썬/Python] 백준 11727번 2×n 타일링 2

11727번: 2×n 타일링 2

---

문제

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

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

입력

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

출력

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

예제 입력

2

예제 출력

3

풀이

import sys
input = sys.stdin.readline

# 입력 받기
n = int(input())

# 초기값 설정
lst = [1, 3]

# 동적 계획법을 사용한 방법의 수 계산
for i in range(2, n):
    lst.append(lst[i-1] + 2 * lst[i-2])

# 결과 출력
print(lst[-1] % 10007)

 

2×n 크기의 직사각형을 채우는 방법의 수를 저장하는 리스트 lst를 초기화하고,

점화식 lst[i] = lst[i-1] + 2 * lst[i-2]를 통해 각 단계의 방법의 수를 계산한다.
lst[-1]은 2×n 크기의 직사각형을 채우는 방법의 수를 나타내며, 10007로 나눈 나머지를 출력한다.

시간 복잡도 : 반복문을 통해 lst를 구성하므로 O(n)의 시간 복잡도를 가진다.

이 코드는 동적 계획법(Dynamic Programming)을 사용하여 2×n 크기의 직사각형을 채우는 방법의 수를 계산하는 프로그램이다. 주어진 조건에 따라 점화식을 이용하여 결과를 도출하고, 마지막에 10007로 나눈 나머지를 출력합니다. 시간 복잡도는 O(n)이다.