[python] 2×n 타일링 2
문제 설명
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
풀이
2×n 타일링 문제와 똑같은데 딱 조건 하나만 추가되었다.
이번엔 2×2
타일로 채우는 경우의 수도 계산하여야 한다.
- 2x1 타일이 한 칸을 차지
- 1x2 타일이 두 칸을 차지
위 조건에서 - 2x2 타일이 두 칸을 차지
이 조건이 추가된 것이다.
역시나 그림으로 나타내면
위 조건에서
이렇게 2x2 타일이 오른쪽에 가 있는 경우의 수가 추가된다.
이 경우에도 나머지 부분은 n-2
가 되기 때문에
점화식은 다음과 같다.
dp[n] = dp[n-1] + dp[n-2]*2
제출 코드
import sys
n = int(sys.stdin.readline())
dp = [1] * (n + 1)
result = 0
if n == 1:
result = 1
else:
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] * 2
result = dp[n] % 10007
print(result)
Author And Source
이 문제에 관하여([python] 2×n 타일링 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@haremeat/python-2n-타일링-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)