Algorithm/1일 1코테
[🤷♀️ 백준] 11727번. 2xN 타일링 2
대인보우
2020. 11. 13. 14:26
반응형
⛄
문제
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
⛄
답
N = int(input())
a= [0, 1, 3]
for i in range(3, 1002):
a.append(a[i-1] + a[i-2]*2)
print(a[N]%10007)다이나믹 프로그래밍으로 푸는 문제
점화식 세울 때 [마지막으로 들어가는 도형] 기준으로 잡기!
1. 가로가 n-1 남았을 때 들어갈 수 있는 도형은 1x2 밖에 없다.
2. 가로가 n-2 만큼 남았을 때 들어갈 수 있는 도형은 두 가지가 있다.
2-1) 2x1 도형이 2개 들어가는 경우
2-2) 2x2 도형이 1개 들어가는 경우
이걸 토대로 점화식을 세운다
a[i] = a[i-1] + a[i-2]*2
반응형