[백준] 9711번 : 피보나치 – JAVA [자바]

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

9711번: 피보나치

 

---

• 문제

 

 

---

• 문제 풀이

백준 9711번 피보나치는 실버 2 난이도의 DP 문제이다. 그중에서도 피보나치와 나머지를 이용해서 푸는 문제이다. 이 문제에서는 테스트 케이스 T가 주어지고 테스트 케이스마다 정수 p와 q가 주어진다. 그리고 각 테스트 케이스에서 p번째 피보나치 수를 q로 나눈 나머지 값을 출력해주면 된다.

 

이 문제는 얼핏 보면 되게 쉬워 보인다. 하지만 이 문제의 정답 비율은 35.903% 밖에 되지 않는다 (2022년 4월 14일 기준). 아마도 BigInteger를 안 써서 그런 거 같다. p의 범위가 1부터 10,000까지여서 long형을 써도 10,000번째 피보나치 수는 long의 범위를 벗어난다. 따라서 BigInteger를 써야 한다.

 

우선 이 문제를 어떻게 풀었는지 설명해보겠다. 각 테스트 케이스마다 p를 입력받고 이 p의 최댓값, 즉 max를 따로 기록해 놓았다. 왜냐하면 이 max 만큼의 피보나치 수만 구하면 되기 때문이다. 따라서 max p를 저장하고 이 max 만큼만 피보나치 수를 BigInteger 형으로 구했다. 

 

그리고 간단히 각 테스트 케이스마다 p번째 피보나치 수를 q로 나눈 나머지를 StringBuilder에 넣어서 마지막에 한 번에 출력했다.

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
    static BigInteger[] dp;
    static BigInteger zero = new BigInteger("0");

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] ps = new int[t+1];
        BigInteger[] qs = new BigInteger[t+1];
        int max = 0;
        StringTokenizer st;
        for (int i = 1; i <= t; i++) {
            st = new StringTokenizer(br.readLine());
            ps[i] = Integer.parseInt(st.nextToken());
            qs[i] = new BigInteger(st.nextToken());
            max = Math.max(max,ps[i]);
        }
        dp = new BigInteger[10001];
        dp[1] = new BigInteger("1");
        dp[2] = new BigInteger("1");
        for (int i = 3; i <= max; i++) {
            dp[i] = dp[i-1].add(dp[i-2]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= t; i++) {
            sb.append("Case #" + i + ": " + dp[ps[i]].remainder(qs[i]) + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

BigInteger를 쓰면 간단히 풀 수 있는 피보나치 문제였던 거 같다.