728x90
https://school.programmers.co.kr/learn/courses/30/lessons/181186
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
2를 표현하는 방법
3을 표현하는 방법
DP(10) = DP(9) + 2*DP(8) + 5*DP(7)
+ 2*DP(6) + 2*DP(5) + 4*DP(4)
+ 2*DP(3) + 2*DP(2) + 4*DP(1)
+ 2
DP(n)을 구하는데 DP(n-4)부터는 반복되는 구간이 나타나므로 DP(n+3)에서 DP(n)을 빼서 하위 구간을 삭제
DP(13) - DP(10) = DP(12) + 2*DP(11) + 5*DP(10) + DP(9) - DP(7)
이 식을 바꿔보면 DP(13) = DP(12) + 2*DP(11) + 6*DP(10) + DP(9) - DP(7)
즉, 아래와 같은 점화식을 세울 수 있다.
DP(x) = DP(x-1) + 2*DP(x-2) + 6*DP(x-3) + DP(x-4) - DP(x-6)
풀이
def solution(n):
dp=[0]*100001
dp[1]=1
dp[2]=3
dp[3]=10
dp[4]=23
dp[5]=62
dp[6]=170
if n>6:
for i in range(7,n+1):
dp[i] = (dp[i-1] + dp[i-2]*2 + dp[i-3]*6 + dp[i-4] - dp[i-6]) % 1000000007
return dp[n]
728x90