[Silver III] 피보나치 수의 확장 - 1788

문제 링크

성능 요약

메모리: 29864 KB, 시간: 144 ms

분류

다이나믹 프로그래밍, 수학

제출 일자

2024년 2월 24일 19:53:07

문제 설명

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

코드

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

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

• -1000000~1000000 까지를 배열로 0~2000001로 바꿨다고 생각하면 된다.
• 만약 1000000보다 작다면 문제 기준으로는 음수이고, 크다면 양수이다.
• 음수일 경우 F[n]= F[n-1]+F[n-2] 식을 F[n] = F[n+2] - F[n+1]으로 수정했다.