본문 바로가기

알고리즘/DP

[DP/ acmicpc] 이친수


출처 : https://www.acmicpc.net/problem/2193




규칙 : 

1. 처음시작은 무조건 1

2. 1 다음에 1이 올 수 없음

2. 0 다음엔 0, 1 둘다 올 수 있음



점화식 :

D[n] = D[n][0] + D[i, j][1]


D[n][0] = D[n-1][0] + D[n-1][1]    // n자리일때 끝이 0으로 끝날 수 있는 경우는 n-1자리일때 0, 1로 끝나는 경우의 수의 합

D[n][1] = D[n-1][0]                   // n자리일때 끝이 1로 끝날 수 있는 경우는 n-1자리일때 1로 끝나는 경우의 수



정리 -> D[n] = D[n-1][0] * 2 + D[n-1][1]