Sep 022011
 

처음에 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]);

}

}

}

 


 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)

This site uses Akismet to reduce spam. Learn how your comment data is processed.