[백준] 피보나치 문제들

문제1

• n은 90보다 작거나 같은 자연수이다.

2748번: 피보나치 수 2

풀이1

DP → 통과

import java.io.*;
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());

        long[] dp = new long[90+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2 ; i <= N ; i ++)
            dp[i] = dp[i-1] + dp[i-2];
        
        System.out.println(dp[N]);
    }
}

재귀 → 시간 초과

import java.io.*;
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());
        System.out.println(recurFibo(N));
    }

    private static int recurFibo(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return recurFibo(n-1) + recurFibo(n-2);
    }
}

문제2

• n은 10,000보다 작거나 같은 자연수 또는 0이다.

10826번: 피보나치 수 4

풀이2

DP + BigInteger

import java.io.*;
import java.math.*;
public class Main {
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        if(N == 0) sb.append(0);
        else if(N == 1) sb.append(1);
        else{
            BigInteger[] dp = new BigInteger[N+1];
            dp[0] = BigInteger.ZERO;
            dp[1] = BigInteger.ONE;
            for(int i = 2 ; i <= N ; i ++)
                dp[i] = dp[i-1].add(dp[i-2]);
            sb.append(dp[N]);
        }
        System.out.println(sb);
    }
}

문제3

• n은 1,000,000보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

15624번: 피보나치 수 7

풀이3

• DP[i] = (DP[i-1] + DP[i-2]) % 1000000007

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        if(N == 0) sb.append(0);
        else if(N == 1) sb.append(1);
        else{
            long[] dp = new long[N+1];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2 ; i <= N ; i ++)
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
            sb.append(dp[N]);
        }
        System.out.println(sb);
    }
}

문제4

• n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
• 첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

2749번: 피보나치 수 3

풀이4

• 피사노(pisano) 주기
  • 피보나치 수를 나눈 나머지는 항상 주기를 가진다. 이를 피사노 주기(Pisano Period)라 한다.

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int pisano = 1500000;
        long N = Long.parseLong(br.readLine()) % pisano;
        long[] dp = new long[pisano+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2 ; i <= N ; i ++)
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000;
        
        System.out.println(dp[(int) N]);
    }
}