글 읽기 - 시간 초과입니다......

wnsgur1714 4년 전 0

수의 법위가 long long 범위를 넘을 것 같아서 직접 배열을 만들어서 돌렸습니다.

배열을 b에서 a, c에서 b로 넘길 때 시간이 걸려서 그럴까요?

아님 다른 이유로 인해 시간초과가 나온 건가요?

#include <iostream>

using namespace std;

char a[30001], b[30001]; //수를 저장할 배열
char c[30002]; //             " 
bool yes; // 자리수를 넘길건지 알려줌
int na, nb; // a의 자리수, b의 자리수
int num; 

int pluss(){ // 두 수를 더하는 함수입니다
    if(na > nb){
        num = na;
        int cha = na - nb;
        for(int i = na-1 ; i >= 0 ; i--){
            if(i >= cha){
                c[i] += a[i] + b[i-cha];
                if(c[i] >= 10){
                    c[i] -= 10;
                    if(i != 0){
                        c[i-1] += 1;
                    }
                    if(i == 0){
                        yes = true;
                    }
                }
            }
            else{
                c[i] += a[i];
                if(c[i] >= 10){
                    c[i] -= 10;
                    if(i != 0){
                        c[i-1] += 1;
                    }
                    if(i == 0){
                        yes = true;
                    }
                }
            }
        }
    }
    if(na == nb){
        num = na;
        for(int i = na-1 ; i >= 0 ; i--){
            c[i] += a[i] + b[i];
            if(c[i] >= 10){
                c[i] -= 10;
                if(i != 0){
                    c[i-1] += 1;
                }
                if(i == 0){
                    yes = true;
                }
            }
        }
    }
    if(na < nb){
        num = nb;
        int cha = nb - na;
        for(int i = nb-1 ; i >= 0 ; i--){
            if(i >= cha){
                c[i] += a[i-cha] + b[i];
                if(c[i] >= 10){
                    c[i] -= 10;
                    if(i != 0){
                        c[i-1] += 1;
                    }
                    if(i == 0){
                        yes = true;
                    }
                }
            }
            else{
                c[i] += b[i];
                if(c[i] >= 10){
                    c[i] -= 10;
                    if(i != 0){
                        c[i-1] += 1;
                    }
                    if(i == 0){
                        yes = true;
                    }
                }
            }
        }
    }
    return 0;
}

int main(){
    int t;
    cin >> t;
    for(int o = 0 ; o < t ; o++){
        char n[30000]; // 입력될 배열
        cin >> n;    // 입력
        if(n[0] == '1' && n[1] == 0){  // 첫자리가 1이고 두번째 자리가 NULL이면(즉 입력받은 숫자가 1이라면)
            cout << 2 << endl; // 2출력
            continue;
        }
        a[0] = 1;
        b[0] = 1;
        na = 1;
        nb = 1;
        for(int i = 2 ; i <= 100001 ; i++){ // 100000번째 이하이므로 100001번째까지 돌림
            num = 0;
            yes = false;
            pluss();                        // 두 수를 더한다
            for(int j = 0 ; j < nb ; j++){  // a배열에 b를 옮김
                a[j] = b[j];
            }
            na = nb;
            if(yes == true){                   // b배열에 c를 옮김
                b[0] = 1;
                for(int j = 1 ; j <= num ; j++){
                    b[j] = c[j-1];
                    c[j-1] = 0;
                }
                yes = false;
                nb = num+1;
            }
            else{
                for(int j = 0 ; j < num ; j++){
                    b[j] = c[j];
                    c[j] = 0;
                }
                nb = num;
            }
            bool yes = false;
            for(int j = 0 ; j <= nb ; j++){        // 정답인지 비교한다
                if(j == nb){  
                    cout << i+1 << endl;
                    yes = true;
                    break;
                }
                if(b[j] != (int)n[j] - 48){
                    break;
                }
            }
            if(yes == true){
                break;
            }
        }
        for(int i = 0 ; i < nb ; i++){ // 초기화
            b[i] = 0;
            a[i] = 0;
            c[i] = 0;
        }
    }
}

djm03178 4년 전 0

매 케이스마다 더하는 과정을 처음부터 반복할 필요가 없습니다.

wnsgur1714 4년 전 0

아.... 그렇군요! 테스트케이스가 여러 개인걸 생각을 못했었네요...

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

문제

문제

출처

ICPC

시간 초과입니다......

wnsgur1714 4년 전 0

djm03178 4년 전 0

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말