Gustavo는 1,2,3,4 밖에 모른다. 그리고 1과 4를 같은 숫자(1)로 알고있다.
1부터 1000까지의 숫자가 주어진다. 그럼 임의의 숫자 n이 1,2,3,4의 숫자를 사용하여 합을 구성할 때 몇개의 경우의 수가발생하는가?

1을 만드는 개수 : f[1] = 이전숫자 + 1 =(이전개수 *2) = f[0] + f[0] = 2

2를 만드는 개수 : f[2] = (이전숫자+1) , 2 = f[1]*2 + 1 = 5

3을 만드는 개수 : f[3] = (이전숫자+1), (그이전숫자+2), 3 = f[2]*2 + f[1] + 1 = 13

4를 만드는 개수 : f[4] = (이전숫자+1), (그이전숫자+2), (그그이전숫자+3) = f[3]*2 + f[2] + f[1]

그럼 다음과 같은 점화식이 나온다.

if(n >= 4)    :    f[n] = f[n-1]*2 + f[n-2] + f[n-3];
otherwise   :    f[1] = 2,  f[2] = 5,  f[3] = 13

또한 숫자가 매우 방대해지기 때문에 BigInteger class를 사용하여 해결하였다.

이올린에 북마크하기