처음에 C언어로 짰으나 1000을 입력해본 결과 Integer 범위를 넘어서는 것을 알 수 있었다. long long으로 바꿨는데도 실패.. 값이 매우 크다고 느낀 나는 Java의 BigInteger를 사용하여 구현하는 것으로 방향을 바꾸었다.
이 문제의 점화식은 아래와 같다.
f(1) = 2
f(2) = 5
f(3) = 13
f(n) = 2 * f(n-1) + f(n-2) + f(n-3)
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static BigInteger[] Data = new BigInteger[1002];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Data[1] = new BigInteger(“2”);
Data[2] = new BigInteger(“5”);
Data[3] = new BigInteger(“13”);
while (scan.hasNext())
{
int n = scan.nextInt();
if (n > 3)
{
for (int i = 4; i<=n; i++)
{
if (Data[i] != null)
continue;
Data[i] = Data[i-1].shiftLeft(1).add(Data[i-2]).add(Data[i-3]);
}
}
System.out.println(Data[n]);
}
}
}