글 읽기 - string으로 계산하는 방식으로 진행했는데 시간초과가 뜹니다.

wijihye 3년 전 0

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

위의 큰 수 A+B 문제를 풀었던 방식으로 문자열 처리를 통해 한자리식 계산해주는 식으로 큰 수를 처리하고자 했는데 어딘가에서 시간초과가 뜹니다..ㅠㅠㅠㅠㅠ 문자열을 더해주는 방식에서 문제가 있었던 걸까요..

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

string fib_4(string a, string b) {

    if (a.size() < b.size()) {
        string c = "";
        for (int k = 0; k < b.size() - a.size(); k++) {
            c += '0';
        }
        a = c + a;
    } // 문자열 자릿수 맞춰주기

    int carry = 0;
    int temp = 0;
    string d = "";

    for (int j = a.size() - 1; j >= 0; j--) {

        int tempa = a[j] - '0';
        int tempb = b[j] - '0';

        temp = tempa + tempb + carry; // 한글자씩 계산용
        if (carry > 0) carry--; // 올림수 계산

        if (temp >= 10) { // 만약 올림수가 발생하면..
            carry++;
            temp %= 10;
        }
        d = (char)(temp + '0') + d; // 최종 문자열에 합해주기
    }

    if (carry > 0) d = "1" + d; // 맨 마지막 올림수 체크

    return d;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    string s[10001];
    s[0] = "0";
    s[1] = "1";

    for (int i = 2; i <= n; i++) {
        s[i] = fib_4(s[i - 2], s[i - 1]);
    }

    cout << s[n];

    return 0;
}

sillysillyman 8달 전 0

d = "1" + d;

이런 경우는 이미 있는 d의 맨 앞에 "1"을 추가하는 것이 아닌 d 값을 복사하기 때문에 그만큼 연산 횟수가 늘어납니다.

대신에 d.insert(0, "1") 이런 식으로 하면 통과 될 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

string으로 계산하는 방식으로 진행했는데 시간초과가 뜹니다.

wijihye 3년 전 0

sillysillyman 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말