[C++로 풀이] 피보나치 수⭐⭐

📌 피보나치 수

난이도 ⭐⭐

🚀 문제

동적 계획법으로 풀어야 시간 초과 안난다.. ^ _ㅠ⭐

🚀 내 풀이

✈ 1차 풀이 ❌

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<int> fibonacci(n + 1);
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    
    for(int i = 2; i <= n; i++)
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    
    return fibonacci[n] % 1234567;
}

피보나치 수는 n이 조금만 커져도 그의 피보나치 수가 어마어마하게 커진다. 44만 되도 그 피보나치 수가 int가 표현할 수 있는 최대 수인 약 21억을 넘은 약 30억이 되버린다고 한다. n이 44 이상만 되도 오버플로우가 되버릴테니 44이상부턴 fibonacci[i]에는 잘못된 값이 차차 담기게 된다. 이 상태에서 1234567 으로 나눈 나머지를 구해봤자 잘못된 값에 나누는 셈이니 달라지는건 없다.

문제에서 1234567 으로 나눈 나머지를 구하라고 한 것은 오버플로우가 일어나지 않고 fibonacci[i]에 담길 수 있도록 한 문제의 배려다.

✈ 2차 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<int> fibonacci(n + 1);
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    
    for(int i = 2; i <= n; i++)
        fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 1234567;
    
    return fibonacci[n];
}

(fibonacci[i - 1] + fibonacci[i - 2]) % 1234567는 (fibonacci[i - 1] % 1234567) + (fibonacci[i - 2]) % 1234567) 과도 같다. 어차피 진짜 피보나치 수는 int 에 담을 수가 없기 때문에.. 피보나치수가 1234567 이상을 넘어간다면 진짜 피보나치 수와는 다른 수가 되겠지만 문제에선 잘못된 값이긴 해도 fibonacci[i]에 123456 이하의 오직 int 만 담길 수있도록 장치를 설정해둔 것 같다. (실제 44의 피보나치 수는 2,971,215,073 이지만 위 코드로 44의 피보나치 수를 구하면 174677이 나온다.문제에선 이를 정답처리 하기로 한 것이다.)

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기