🗃️문제 설명
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어, 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000)
첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
🖥️코드
import sys
input = sys.stdin.readline
# N = 1 : 1가지
# N = 2 : 3가지
# N = 3 : 5가지
N = int(input())
memoization = [0] * 1001
memoization[1] = 1
memoization[2] = 3
for n in range(3, N+1):
memoization[n] = (memoization[n-1] + memoization[n-2] * 2) % 796796
print(memoization[N])👉DP 문제 : 큰 문제를 작은 문제 단위로...
👉위 문제에서 DP를 적용하는 방법
- (i)번째 타일을 채우는 경우의 수
- (i-1)번째까지 타일을 채웠다고 가정할 때, 마지막은 2 x 1 타일로만 채우면 된다.
- (i-2)번째까지 타일을 채웠다고 가정할 때, 2 x 2 타일 하나 혹은 1 x 2 타일 2장으로 채우면 된다.
🔒문제 출처 및 참고 코드
이것이 코딩테스트다 with 파이썬 - 바닥 공사
모범 답안 - 바닥 공사
