[BOJ] 11726 2xn 타일 직사각형

date

Jul 1, 2023

slug

boj-11726

author

status

Public

문제

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

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

문제풀이

피보나치 수를 10007로 나눈 나머지를 구하면 된다.

arr[n] = arr[n-1] + arr[n-2]

why?

n-1의 직사각형 패턴에 |이 추가된 형태

n-2의 직사각형 패턴에 = 혹은 ||이 추가된 형태, 이때 =이 고정

파이썬 문제풀이 코드


arr = []
arr.append(0) #0
arr.append(1) # 1
arr.append(2) # 2
arr.append(3) # 3

n = int(input())

for i in range(4, 1001):
    arr.append((arr[i-1] + arr[i-2])%10007)
    
print(arr[n])

시간복잡도

피보나치 수를 DP로 구현했기 때문에 O(n)

입력

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

출력

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

[BOJ] 11726 2xn 타일 직사각형

문제

문제풀이

입력

출력

예제 입력

예제 출력

알고리즘 분류