글 읽기 - 1850번 c언어 시간초과 질문입니다.

purpose 6년 전 0

a와 b가 서로소이면 1이 최대공약수이고, 나머지는 유클리드 호제법 사용하면 된다고 생각해서 그대로 구현해보았는데요.

어디서 시간을 잡아먹는 건지 시간초과가 계속 나옵니다.. 힌트 좀 주실 수 있을까요..?

#include <stdio.h>

#define swap(a, b){ int t; t = a; a = b; b = t;}

int gcd(int a, int b){
    int c;
    if(a < b) swap(a, b);
    while(b){
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int Getnum(int a){
    int num = 0;
    while(a){
        a--;
        num = num * 10 + 1;
    }
    return num;
}

int main(void){
    int a, b;
    scanf("%d %d", &a, &b);
    int num;
    int Cdiv; // 최대공약수
    Cdiv = gcd(a, b);
    if(Cdiv == 1){
        printf("%d", num);
    }else{
        num = Getnum(Cdiv);
        printf("%d", num);
    }
}

Green55 6년 전 0

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 19자리를 넘지 않는 자연수이다.

입력되는 수가 10억이면, A는 10억이 아니라 1이 10억개 있는 수가 됩니다. int가 저장 가능한 범위를 아득하게 넘어갑니다.

purpose 6년 전 0

여기서 a를 11111111.....로 바꾼 값을 저장하지 않고

천만자리 이하의 수가 출력된다고 했으니 최대공약수가 천만자리 이하로 주어지고, 따라서 a와 b의 최대공약수가 1로 표현되어 봐야 11111111일 테니

괜찮지 않나요..??

먼저 최대공약수를 구하고 그것을 1로 바꾼 값을 출력했는데...ㅠㅠㅠ

Green55 6년 전 1

죄송합니다 코드를 제대로 안 읽어서 좀 착각했네요...

어쨌든 입력되는 수가 9999999999999999999 까지 가능하기때문에 int로 입력을 받으면 안되는건 맞습니다.

그리고 Cdiv가 1일경우 num에 아무 값도 들어가지 않아 쓰레기값이 출력됩니다.

제가 이 문제를 풀지 않아서 알고리즘 자체가 맞는지는 모르겠는데 일단 실수하신 부분이 몇개 보여서 적어봤습니다.

jh05013 6년 전 1

Getnum도 int 범위가 아닙니다.

purpose 6년 전 0

문제를 알아서 이렇게 소스를 수정했는데 출력초과가 뜨네요....

출력값 천만자리 이하라고 했으니 Cdiv 최대가 1000일테고..

음... 다른 컴파일러에 돌리면 나오는데 이유가 뭘까요..?

그리고 for문을 이용해서

for(i = 0; i < Cdiv; i++){

printf("1");

}

를 하니까 출력초과가 아니라 틀렸습니다가 나오는데 왜 다르게 나오는지 이유도 알고싶어요~~

#include <stdio.h>

#define swap(a, b){ int t; t = a; a = b; b = t;}

int gcd(int a, int b){ // 유클리드 호제법.
    int c;
    if(a < b) swap(a, b);
    while(b){
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main(void){
    long long int a, b;
    scanf("%lld %lld", &a, &b);
    int Cdiv; // 최대공약수
    Cdiv = gcd(a, b);
    while(Cdiv){
        Cdiv--;
        printf("1");
    }
}

Green55 6년 전 2

GCD가 매개변수로 int를 받네요.

아마 둘이 다른 결과가 나온건 GCD의 매개변수 a,b가 오버플로우가 났을 때 Cdiv에 음수값이 저장되서 그런게 아닐까 싶습니다.

purpose 6년 전 0

감사합니다!! 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

1850번 c언어 시간초과 질문입니다.

purpose 6년 전 0

Green55 6년 전 0

purpose 6년 전 0

Green55 6년 전 1

jh05013 6년 전 1

purpose 6년 전 0

Green55 6년 전 2

purpose 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말