master1511   3년 전

문제를 잘 모르겠어서 노트에 하나하나 다 써서 구해보니

(N>3)

arr[N] = arr[N-1]+arr[N-2]+arr[N-3]

이라는걸 발견해서 문제는 풀었긴 풀었는데요,


대채 왜 1,2,3으로 수를 만드는 이 문제가

위의 점화식에 해당이 되는걸까요?


bupjae   3년 전

예를 들어, 15를 만들기 위해서는 다음과 같은 방법으로 만들 수 있습니다.


15 = (12를 만들기 위한 수많은 방법) + 3

15 = (13을 만들기 위한 수많은 방법) + 2

15 = (14를 만들기 위한 수많은 방법) + 1


이 방법들은 15를 만들기 위한 각각 서로 다른 방법이기 때문에,

(15를 만드는 방법의 수) = (12를 만드는 방법의 수) + (13을 만드는 방법의 수) + (14를 만드는 방법의 수) 가 됩니다.

댓글을 작성하려면 로그인해야 합니다.