백준 10826 피보나치 수 4

백준 10826 피보나치 수 4

이번 문제는 피보나치수를 구하는 간단한 문제였는데, c++ 에서 가장 큰 수 의 범위를 그냥 넘겨버려서 unsigned long 을 한다고 해결되는 문제가 아니었다.ㅜ 다른 언어는 상관이 없나 레벨이 엄청 낮았는데, 실버 5를 받을 만큼 쉬운 문제는 분명 아니다!

• 이 문제를 해결하기 위해 문자열로 입력을 받아 더하는 방식을 구현해야 했다.

string string_add(string x, string y)
{
    int num;
    int carry = 0;
    string result;

    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());

    while (x.length() < y.length()) {
        x += '0';
    }
    while (x.length() > y.length()) {
        y += '0';
    }

    for (int i = 0; i < x.length(); ++i) {
        num = (x[i] - '0' + y[i] - '0' + carry) % 10;
        result += to_string(num);
        carry = (x[i] - '0' + y[i] - '0' + carry) / 10;
    }
    if (carry != 0) {
        result += to_string(carry);
    }

    reverse(result.begin(), result.end());

    return result;
}

• 987과 1597을 더해보자.

• 우선 reverse 를 사용해 숫자를 뒤집어 주고, 만약 자릿수가 다르다면 같게 통일 해주기 위해 뒤에 다 0을 붙여준다.

• 7890, 7951 가 만들어 질 것 이다.

• 이제 string을 0 부터 문자열 길이만큼 돌면서 숫자로 바꿔 더하고, 그 값이 10보다 클 경우 일의 자리 수만 저장하고 자릿수가 올라갈 때 1을 증가시켜 준다.

• 이 과정을 끝날 때까지 반복하면 된다!!!