바닥 공사

이 문제는 이것이 코딩테스트다 223페이지 문제이다.

아래는 나의 코드이다.

 

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

dp[0]=0
dp[1]=1
dp[2]=3

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

print(dp[N]%796796)

 

 

아래는 예시코드이다.

# 정수 N을 입력 받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

# 계산된 결과 출력
print(d[n])