문제
음수까지 확장된 피보나치 수 F(n)을 구하라. F(n) = F(n-1) + F(n-2)이므로 F(-n) = F(-n+2) - F(-n+1)로 계산된다. 결과를 10^9로 나눈 나머지를 출력한다.
입력
정수 N이 주어진다 (-1,000,000 이상 1,000,000 이하).
출력
첫째 줄에 양수면 1, 0이면 0, 음수면 -1을 출력하고, 둘째 줄에 절댓값을 10^9로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
-2 | -1 1 |
풀이
인덱스를 오프셋으로 양수화하여 DP 배열에 양/음 방향 피보나치를 계산한다.
- 인덱스에 1,000,000을 더해 음수를 양수 인덱스로 변환한다
- N이 양수면 정방향 점화식, 음수면 역방향
F(i) = F(i+2) - F(i+1)을 사용한다 - 결과의 부호를 판별하여 첫 줄에 출력하고, 절댓값을 MOD로 나눈 나머지를 출력한다
핵심 아이디어: 음수 피보나치는 F(-n) = (-1)^(n+1) * F(n)의 성질을 가지며, 역방향 점화식으로 구한다.
코드
package day499;
import java.io.*;
public class Day462BOJ1788피보나치수의확장 {
static final int MOD = 1_000_000_000;
static final int SET = 1_000_000;
static int N, ans = 1;
static long[] dp = new long[2000001];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()) + SET;
dp[SET + 1] = 1;
if (N < SET) {
for (int i = SET - 1; i >= N; i--) {
dp[i] = (dp[i + 2] - dp[i + 1]) % MOD;
}
} else {
for (int i = SET + 2; i <= N; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
}
if (dp[N] == 0)
ans = 0;
else if (dp[N] < 0)
ans = -1;
System.out.println(ans);
System.out.print(Math.abs(dp[N]));
}
}복잡도
- 시간: O(|N|)
- 공간: O(|N|)