[이코테 - 다이나믹 프로그래밍] 바닥 공사

• 문제 설명

N을 입력받고 2xN 크기의 바닥을 위 3가지 종류의 덮개로 채워야 할 때의 경우의 수를 출력하면 된다.

 

 

위를 참고하여 점화식을 유도해낸다음 코드에 적용시키면 된다.

 

 

 

 

• 문제 코드

N = int(input())
dp = [0]*(N+1)

dp[1] = 1 #2x1 짜리 하나 총 1가지
dp[2] = 3 #2x1 짜리 두개,1x2 짜리 두개, 2x2 짜리 하나 총 3가지

for i in range(3,N+1):
    dp[i] = (dp[i-1] + 2*dp[i-2]) % 796796
print(dp[N])

 

점화식만 문제를 보고 뽑을 줄 알고  초기 설정만 잘해주면 어렵지 않게 dp문제를 풀 수 있을 것 같다.

 

• 관련 문제

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

• 제출 코드

import sys
input = sys.stdin.readline
N = int(input())
dp = [0]*(1001)

dp[1] = 1 #2x1 짜리 하나 총 1가지
dp[2] = 2 #2x1 짜리 두개,1x2 짜리 두개 총 2가지

for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[N])