[백준] 9711번: 피보나치(JAVA)

▶ 문제

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

9711번: 피보나치

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

제한

• 1 ≤ P ≤ 10,000
• 1 ≤ Q ≤ 2,000,000,000

---

▶ 풀이

 - JAVA

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        BigInteger[] dp = new BigInteger[10001];
        dp[1] = dp[2] = new BigInteger("1");
        for(int i = 3; i <= 10000; i++){
            //a.add(b): a+b (a,b는 BigInteger)
            dp[i] = dp[i-1].add(dp[i-2]);
        }

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= T; i++){
            st = new StringTokenizer(br.readLine());
            int P = Integer.parseInt(st.nextToken());
            int Q = Integer.parseInt(st.nextToken());

            sb.append("Case #").append(i).append(": ");
            //a.remainder(b): a%b (a,b는 BigInteger)
            //BigInteger.valueOf(a): a를 BigInteger로 형변환
            sb.append(dp[P].remainder(BigInteger.valueOf(Q))).append("\n");
        }

        System.out.print(sb);
    }
}

---

▶ 메모

long형을 써도 값이 long의 범위를 벗어나니 BigInteger를 사용,

DP와 BigInteger의 메소드(add, remainder, ValueOf)를 사용하여 풀면 된다.