[BOJ]1788번 : 피보나치 수의 확장

https://www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

 

분류 : 구현, 수학

 

일반적인 피보나치수열 확장으로 음수까지 계산하는 문제

하지만 단순하게 N이 양수일 때 , 음수일 때 각각 10까지 나열해보니 규칙을 찾을 수 있었다.

import java.io.*;
import java.math.*;
import java.util.*;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {

    static PrintWriter out;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int N = sc.nextInt();
        int MN = Math.abs(N);
        long[] fib = new long[MN+1];
        for(int i=0;i<fib.length;i++)
        {
            if(i==0 || i==1)
            {
                fib[i] = i;
            }
            else{
                fib[i] = (fib[i-1]+fib[i-2])%1000000000;
            }
        }
        if(MN%2==0 && N<0)
        {
            out.println(-1);
            out.println(fib[MN]);
        }        
        else if(MN==0)
        {
            out.println(0);
            out.println(fib[MN]);
        }
        
        else
        {
            out.println(1);
            out.println(fib[MN]);
        }
        out.flush();
    }
}

 

fib[i] = (fib[i-1]+fib[i-2]) %1000000000 부분을 fib[i] = fib[i-1] %1000000000+fib[i-2] %1000000000 식으로 계산했다가 자꾸 틀렸다...