문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
문제 풀이
규칙을 찾으면 되는 문제였다.
위와 같이 2x4 타일링까지 찾아본 결과,
N >= 3 일 때, 2xN 타일링은 다음과 같은 규칙을 갖는다.
1. 2*(N-1) 타일링에 2*1 타일을 하나 붙인다.
2. 2*(N-2) 타일링에 1*2 타일을 두 개 붙인다.
3. 2*(N-2) 타일링에 2*2 을 하나 붙인다.
따라서, DP 식은 dp[n] = dp[n-1] + 2*(dp[n-2])
이다.
작성 코드
import sys
input = sys.stdin.readline
dp = [0, 1, 3]
for i in range(3, 1001):
dp.append((dp[i-1] + dp[i-2]*2) % 10007)
n = int(input())
print(dp[n])
'Problem Solving' 카테고리의 다른 글
[백준] 16194 - 카드 구매하기2 in 파이썬 (0) | 2022.09.04 |
---|---|
[백준] 11052 - 카드 구매하기 in 파이썬 (0) | 2022.09.04 |
[프로그래머스] level 1 - 크레인 인형뽑기 게임 in 파이썬 (0) | 2022.08.18 |
[백준] 17299 - 오등큰수 in 파이썬 (0) | 2022.08.12 |
[백준] 1406 - 에디터 in 파이썬 (0) | 2022.08.07 |