백준 17271. 리그 오브 레전설 (Small)

tose33 2022. 7. 18. 13:50

17271번: 리그 오브 레전설 (Small)

규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 N초의 시간 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다. A 스킬의 시전 시간은 1

www.acmicpc.net

d[i] : 게임이 i초 진행됐을때 가능한 스킬의 조합의 갯수

점화식:

d[i] = d[i-1] + d[i-M]

주의할점:

- 최초에 d[1], d[M] = 1 이다.

- d[i-M]에서 i-M이 음수가 될때는 0으로 처리한다.