Algorithm/1일 1코테
[🤷♀️ 백준] 11726번. 2xn 타일링 (PYTHON)
대인보우
2020. 11. 13. 13:10
반응형
📌
문제
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
📌
답
# 런타임 에러
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 인 걸 알 수 있다.
이걸 이용해 각 리스트에 저장해주면 된다.
반응형