백준 10826번 [피보나치 수 4](C++) -yes6686- 티스토리

백준 문제 풀이: 10826 [피보나치 수 4]

---

문제 링크: https://www.acmicpc.net/problem/10826

문제 설명:

피보나치 수열의 n번째 값을 계산하는 문제입니다. 단, n이 매우 커질 수 있으므로, 결과를 저장할 자료형으로 문자열을 사용해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string dp[10001]; // 각 피보나치 수를 문자열로 저장

// 두 문자열 숫자를 더하는 함수
string sum(string a, string b) {
    string result = "";
    int carry = 0; // 올림 수

    // 문자열의 끝에서부터 더하기
    while (a.size() || b.size()) {
        int num1 = 0, num2 = 0;
        if (a.size()) {
            num1 = a.back() - '0'; // 문자 → 숫자
            a.pop_back();
        }
        if (b.size()) {
            num2 = b.back() - '0'; // 문자 → 숫자
            b.pop_back();
        }
        // 현재 자리의 합 계산
        int currentSum = num1 + num2 + carry;
        result += to_string(currentSum % 10); // 현재 자리수
        carry = currentSum / 10; // 올림 수 계산
    }

    // 마지막으로 올림 수가 남아있다면 추가
    if (carry) {
        result += "1";
    }

    // 문자열 뒤집기
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n;
    cin >> n;

    // 초기 피보나치 값 설정
    dp[0] = "0";
    dp[1] = "1";

    // 피보나치 수 계산
    for (int i = 2; i <= n; i++) {
        dp[i] = sum(dp[i - 1], dp[i - 2]);
    }

    // 결과 출력
    cout << dp[n] << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 문자열로 표현된 두 큰 숫자를 더하는 방식을 구현하여 피보나치 수열을 계산합니다.
• 구현 세부사항:
  • sum(string a, string b): 두 문자열 숫자를 더해 새로운 문자열로 반환
  • 각 자리의 숫자를 더하고, 올림수를 반영하며 결과 문자열을 구성
  • DP 배열 dp[i]: i번째 피보나치 수를 저장
• 시간 복잡도 분석: O(n × L)
  • n: 피보나치 수의 인덱스
  • L: 피보나치 수의 자리수

---

결과

피보나치 수열의 매우 큰 수를 정확히 계산하고 출력할 수 있습니다. 문자열 연산을 활용하여 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!