글 읽기 - c++ 시간초과 질문

kscn 2년 전 0

제가 보기엔 시간초과가 날만한곳이 없는것같은데
시간초과가 나오네요

어디가 문제일까요

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

int GCD(int a, int b){
    int gcd = 2;
    bool irreducible = 1;
    for(int i = 1; i <= min(a, b); i++){
        if(a % i == 0 && b % i == 0){
            gcd = i;
            irreducible = 0;
        }
    }
    if(irreducible) return -1;
    else return gcd;
}

struct fraction{
    int numerator;
    int denominator;
    
    void plus(fraction a, fraction b){
        int num, den;
        den = a.denominator * b.denominator;
        num = a.numerator * b.denominator + b.numerator * a.denominator;
    
        int gcd = GCD(den, num);
        if(gcd != -1){
            den /= gcd;
            num /= gcd;
            this->denominator = den;
            this->numerator = num;
        }
        else{
            this->denominator = den;
            this->numerator = num;
        }
    }
    
    fraction(int a, int b){
        this->numerator = a;
        this->denominator = b;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int an, ad, bn, bd;
    cin >> an >> ad >> bn >> bd;
    fraction a(an, ad);
    fraction b(bn, bd);
    
    fraction res(0, 0);
    res.plus(a, b);
    cout << res.numerator << " " << res.denominator;
    
    return 0;
}

djs100201 2년 전 0

GCD의 시간복잡도가 너무 커요

yeop77 2년 전 0

min(a,b) 함수를 굳이 갖고와서 쓸 필요가 있을까요
그냥 작은거 확인해서 그걸로 바로 쓰세요

djs100201 2년 전 1

min(a,b)의 호출은 시간복잡도에 크게 영향을 미치지 않습니다.
유클리드 호제법을 이용해서 O(logn)에 구해야 해요.

kscn 2년 전 0

감사합니다 유클리드 호제법으로 GCD구하니 통과되네요

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

문제

문제

출처

ICPC

c++ 시간초과 질문

kscn 2년 전 0

djs100201 2년 전 0

yeop77 2년 전 0

djs100201 2년 전 1

kscn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말