백준 11726 - 2×n 타일링 (Python)
2024. 2. 6. 00:58ㆍ알고리즘
문제
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
풀이
n = int(input())
dp = [-1]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-2] + dp[i-1]
print(dp[n]%10007)
이 문제의 정답 코드는 피보나치 수열을 구하는 방식과 동일하다.
그 이유를 살펴보자면
2×N을 채우는 경우의 수는 아래 두가지로 나뉜다.
1) 2×(N-2)를 채우고 = 모양을 더하는 경우
2) 2×(N-1)을 채운 뒤 l 모양을 더하는 경우
N=1일 때 경우의 수는 1, N=2일 때 경우의 수는 2이므로 해당 값을 기본값으로 두고 이전 두 경우의 수를 더하는 것이므로 피보나치 수열과 동일한 경향을 보인다.
파이썬 코드에서는 동적계획법을 활용하여 N번째 피보나치 수를 구하는 코드를 작성한 뒤, 결과값을 10007로 나눈 값을 출력했다.