백준 4150 피보나치 수(c++)

https://www.acmicpc.net/problem/4150

4150번: 피보나치 수

 

 

문제를 읽어보면 알 수 있듯이 숫자의 길이가 100자리가 넘어간다.

이런 문제는 long long int도 메모리 초과가 뜨기 때문에 어떻게 풀까? 고민해봐야 된다. 

 

정답은 문자열string을 쓰면 되는데 문제를 풀 때 피보나치 수를 직접 적어보면서 코드를 어떻게 짤지 고민을 해봤다. 

 

 

//1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597  피 보나 치수

 

#include <iostream>
#include <string>
using namespace std;
int main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    string str="1";
    int n;
    cin >> n;
 
    string copy;
    copy = str;
    string tmp;
    for (int i = 2; i < n; i++) {
        tmp = str;
        for (int j = 0; j < copy.size(); j++) {
            str[j] += (copy[j]-'0');
            
            if (j < copy.size() && str[j]>'9') {
                str[j] -= 10;
                if (j+1 < str.size())
                    
                    str[j + 1] += 1;
                else if (j+1 == copy.size())
                    str += '1';
            }
            
        }
        copy = tmp;
    }
 
 
    for (int i = str.size(); i != 0; i--) {
        cout << str[i-1];
    }
 
 
    return 0;
}

코드를 설명하면 string은 수를 더했을 때 1의자릿수를 배열의 0번째 10의 자리 수를 배열의 1번째 넣는다고 생각했다. 그리고 1의 자리수 부터 더해갔을때 만약에 그 수가 '10'보다 크면 10을 빼주고 다음자리수에 1을 더해준다. 만약에 다음 자리수를 넣을 배열이 존재하지 않는다면? 그 문자열에 '1'을 추가해준다. 

 

3줄 요약

1. 자릿수 거꾸로 해서 더해줌 (더하기에 용이)

2. 더했을 때 '10'을 넘는지 확인 넘으면 다음 배열 더해줌

3. 다음 배열 더할 조건이 왔을 때, 배열의 크기를 초과하면 문자 '1'을 추가해줌