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

문제 출처 - Baekjoon Online Judge

문제는 여기

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. BigInteger형으로 만든 dp 배열에 0번과 1번에 각각 0, 1을 담아준다.

2. 피보나치 점화식을 사용하여 dp 배열을 채워준다.

3. n번만큼 반복하여 p와 q의 값을 입력받고 dp[p]를 q로 나눈 나머지 값을 출력한다.

[접근]

1. 피보나치를 모두 구해주고 해당 값을 입력받은 q로 나눈 나머지를 출력하면 되겠다고 생각하였다.

2. 1. 번의 방식으로 풀었지만 틀렸다고 나와 찾아보니 BigInteger형을 사용하여야 한다고 되어있어 이를 이용하여 문제를 해결하였다.

[코드]

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

public class Main {
	static BigInteger[] dp = new BigInteger[10001];
	static int n;
	static int p;
	static BigInteger q;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		dp[0] = new BigInteger("0");
		dp[1] = new BigInteger("1");
		
		for (int j = 2; j < dp.length; j++) {
			dp[j] = dp[j - 1].add(dp[j - 2]);
		}
		
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			p = Integer.parseInt(st.nextToken());
			q = new BigInteger(st.nextToken());
			
			System.out.println("Case #" + i + ": " + dp[p].remainder(q));
		}
	}
}