바닥공사

출처::  https://hiruby.tistory.com/266?category=396294 

분류:: 다이나믹 프로그래밍

 

1. 문제 이해 및 해결과정

  1) 왼쪽부터 i-1의 길이가 덮개로 이미 채워져 있으면 2*1 덮개를 채우는 하나의 경우의 밖에 존재 하지 않음

  2) 왼쪽부터 i-2의 길이가 덮개로 이미 채워져 있으면 1*2 덮개를 2개 덮는경우, 2*2 덮개 하나를 넣는 경우로 2가지가 존재한다

  3) n-2 미만의 길이에 대해서 고려할 필요가 없다. 사용할 수 있는 덮개의 최대가 2*2이기 때문이다. 

  => ai=a(i-1) + a(i-2) + a(i-2)

 

2. 풀이방법

 1. 다이나믹 프로그래밍

#바닥 공사
#
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[0]*1001
dp[1]=1
dp[2]=3

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

print(dp[n])

 

3. 오답원인

 

4. 알게된 점