[Java] 1788번 - 피보나치 수의 확장

문제 링크 : 백준 1788번 - 피보나치 수의 확장

 

아래 점만 주의하면 된다.

1. 어차피 음수 -N과 양수 N의 피보나치 수의 절댓값은 같으므로 첫번째줄 출력만 잘 처리해주고 나머지 로직은 음수인 경우 절댓값으로 변환 후 똑같은 로직으로 처리하면 된다.

2. n이 1,000,000,000을 넘지 않도록 나머지 연산을 잘 처리해준다.

 

 

N이 음수인 경우 2로 나누어 떨어지는 경우에만 F(N)이 음수가 된다.

 

 

피보나치 수 공식을 이용해 -5부터 5까지만 구해보자.

n > 1 이지만 우린 음수로 확장하였기 때문에 |n| > 1 을 적용해서 계산하면 된다.

 

F(0) = 0

F(1) = 1, F(-1) = 1

F(2) = 1, F(-2) = -1

F(3) = 2, F(-3) = 2

F(4) = 3, F(-4) = -3

짝수인경우에만 음수가 되는 것을 확인할 수 있다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
if (N < 0 && N % 2 == 0) {
    System.out.println("-1");
} else if (N == 0) {
    System.out.println("0");
} else {
    System.out.println("1");
}
N = Math.abs(N);
long[] fibo = new long[N + 2];
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i <= N; i++) {
    fibo[i] = (fibo[i - 1] % MOD + fibo[i - 2] % MOD) % MOD;
}
System.out.println(fibo[N]);