BOJ_피보나치 수6_11444

문제 링크

성능 요약

메모리: 14308 KB, 시간: 108 ms

분류

분할 정복을 이용한 거듭제곱, 수학

제출 일자

2024년 12월 13일 15:34:15

문제 설명

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

풀이

• 느낀점
  시간초과 후 해결방법을 전혀 모르겠어서 풀이를 찾아봤는데, 이해하고 직접 성공하는데 이틀 걸렸다.
  결국 행렬곱셉 방식으로 풀지 않았지만, 이해해가는 과정에서 사용해볼 수 있어서 좋았다.
• 설계 시간: 2일
  

💡 설계 아이디어

• 행렬곱셈을 이용해 피보나치 수열을 공식화 하면 단순히 모든 수를 더해가며 수열을 구하는 것보다 빠르다. (분할정복)
• 행렬곱셈을 모르더라도 같은 모양의 공식을 만들 수 있었다. (이것도 참고하고 배움)
• 문제는 n이 짝수일 때와 홀수일때를 나누어 계산한다는 점인데 홀수일 때의 가정을 n = 2k+1로 뒀을때, 도달 가능한 범위가 3이상임으로 완전하지 않아 2k-1로 두는 것이 오류가 없는 것으로 보였다.
• 메모이제이션에 배열을 사용하기에는 배열길이 한계가 있어서 Map으로 구현했다.
  

코드

• 구현 시간: 2시간

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 피보나치 수 6_11444
 * Date: 2024.12.06
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static Map<Long, Long> dp;
	static final int MOD = 1_000_000_007;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(br.readLine());

		dp = new HashMap<>();
		dp.put(0L, 0L);
		dp.put(1L, 1L);
		dp.put(2L, 1L);
		dp.put(3L, 2L);
		long answer = fibo(n);

		bw.write(String.valueOf(answer));

		bw.flush();
		bw.close();
		br.close();
	}

	public static long fibo(long n) {

		if (dp.containsKey(n)) return dp.get(n);

		long result = 0;
		if (n % 2 == 0) {
			result = fibo(n / 2) * (fibo(n / 2 + 1) + fibo(n / 2 - 1));
		} else {
			result = fibo((n + 1) / 2) * fibo((n + 1) / 2)  % MOD + fibo((n - 1) / 2) * fibo((n - 1) / 2)  % MOD;
		}

		result %= MOD;
		dp.put(n, result);
		return result;
	}
}