[🤷‍♀️ 백준] 11727번. 2xN 타일링 2

Algorithm/1일 1코테 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

Dainbow's Log