바닥공사 [dp]
# 가로길이 n, 세로길이 2인 바닥
# 1*2, 2*1, 2*2 타일로 덮개를 채우는 모든 경우의 수
# n-1일 때의 타일을 n번째의 타일에서 이용 -> DP
n=int(input())
dp=[0]*(1001)
dp[0]=1 # 2*1 타일 채우는 경우의 수
dp[1]=3 # 2*2 타일 채우는 경우의 수
# dp[2]=dp[0]+dp[1]+1
for i in range(2,n):
dp[i]=(dp[i-1]+2*dp[i-2])%796796
print(dp[n-1])
- 점화식을 세우는 법 숙지
- 일반화를 통해 n과 n-1, n-2의 관계식을 찾기
Author And Source
이 문제에 관하여(바닥공사 [dp]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@csy9604/바닥공사-dp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)