자바로 백준 1788 풀기

• 실버 3단계 문제

풀이)

당연하지만 재귀로 풀면 시간 초과가 걸린다.
예를 들어 fib(100)을 계산할 때, fib(99)와 fib(98)의 값을 알아야 하는데 각 노드마다 fib(1) fib(2) .... fib(98) 을 모조리 계산해야 하기 때문이다.

fib(98)을 계산하고 배열에 저장하면, fib(99)를 계산할 때 굳이 fib(1) ~ (98) 까지 계산할 필요 없이 fib(98)값을 가져와 연산하면 된다.

내 코드)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		if(n==0){
		    System.out.println("0");
		    System.out.println("0");
		    System.exit(0);
		}
		
		int tmp = Math.abs(n);
		long[] dp = new long[1000001];
		dp[0] = 0;
		dp[1] = 1;
		for(int i = 2; i <= tmp; i++)
	        dp[i] = (dp[i-1]+dp[i-2])%1000000000;
		
		System.out.println((n>0)? "1": (tmp%2==0)? "-1":"1");
		System.out.println(dp[tmp]);
	}
}