백준 > 9711번 > 피보나치 - JAVA

 

 

문제

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

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

 

 

 

코드

 

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

public class JUN9711 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int TC = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        BigInteger[] dp = new BigInteger[10001]; // P의 최댓값이 10000이기에

        dp[0] = BigInteger.valueOf(0);
        dp[1] = BigInteger.valueOf(1);

        for(int i = 2; i <= 10000; i++){
            dp[i] =  dp[i-2].add(dp[i-1]);
        }

        for(int tc = 1; tc <= TC; tc++){
            st = new StringTokenizer(br.readLine());

            int P = Integer.parseInt(st.nextToken());
            int Q = Integer.parseInt(st.nextToken());
            
            sb.append("Case #"+tc+": "+dp[P].remainder(BigInteger.valueOf(Q))+"\n");
        }
        System.out.print(sb);
    }
}

 

 

풀이

 

단순한 문제입니다!

 

다만 주의할 점이 2가지 있습니다.

 

---

 

1. P의 최댓값이 10000이라는 점

 

피보나치를 구하면 

 

int 형으로 하면 P 가 76 정도면 터집니다.

 

그런데

 

long, Long, double 이 int 형보다 사이즈가 훨씬 크다고 해도

 

10000의 피보나치를 구할 수 있을까요?

 

네!

 

없습니다!

 

저 위의 모든 형태의 변수를 사용해도 110 정도만 되면 다 터져버릴겁니다.

(테스트 해보시는 거 추천드립니다.)

 

그래서 우리는 

 

BigInteger 를 써야합니다.

 

Big, 보기만 해도 큰 수를 다루게 생겼습니다.

 

---

2. 1의 이유로 인한 메모리 이슈

 

이 문제의 경우 테스트 케이스 수(T) 가 주어집니다.

 

T만큼 피보나치를 구하다 보면

 

P가 작은 수일때는 괜찮지만

 

큰 수가 주어진다면

 

메모리의 이슈가 생기게 됩니다.

 

 

예를 들어서,

 

T = 10 인데

 

10번 다 P 가 10000이고

 

Q 의 값만 조금씩 바뀌는 경우라면

 

매번 10000의 피보나치 수를 구하는 건 너무 비효율적이고

 

메모리가 버티지 못하겠죠?

 

그리고 DP 를 사용하는 이유가

 

반복되는(중복되는) 연산을 없애서

 

메모리의 이득, 시간적 이득을 얻기 위해선데

 

이렇게 해서는 안되겠죠?

 

 

그래서 애초에 P의 범위가 주어져있으니까

 

맨처음에 피보나치를 10000까지 구해버립니다.

 

그 후에 

 

P, Q 의 값에 따른 결과값만 계산하면

 

메모리의 낭비가 막아지는 겁니다!!!!

 

이렇게만 하면 여유있게 통과하실 겁니다 ㅎㅎ

 

오늘도 봐주셔서 감사합니다.

 

 

 

 

다음에 또 봐요