[🤷‍♀️ 백준] 11726번. 2xn 타일링 (PYTHON)

 

📌

문제

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

📌

답

# 런타임 에러

N = int(input())
a = [0 for _ in range(N+1)]

a[0] = 0
a[1] = 1
a[2] = 2

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

print(a[N]%10007)

# 수정

N = int(input())
a = [0,1,2]

for i in range(3, 1001):
    a.append(a[i-1] + a[i-2])

print(a[N]%10007)

다이나믹 프로그래밍을 이용하는 문제

 

1. 인덱스가 n, 해당 인덱스 값이 경우의 수인 리스트를 생성한다.

 

2. n을 0부터 살펴보면

n=0 일 때 경우의 수 > 0

n=1 일 때 경우의 수 > 1

n=2 > 2

n=3 > 3

n=4 > 5 

n=5 > 8...

살펴보면 n=3일때부터 n = n-1 + n-2 인 걸 알 수 있다.

이걸 이용해 각 리스트에 저장해주면 된다.