[BaekJoon 1850번] 최대공약수(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1850번: 최대공약수

 

 

[문제 설명]

 

 

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

 

 

[입력]

 

 

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63보다 작은 자연수이다.

 

 

[출력]

 

 

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

 

[입출력 예]

 

 

예제 입력	예제 출력
3 4	1
3 6	111
500000000000000000 500000000000000002	11

 

 

[문제 풀이]

 

문제를 보고 입출력 예1, 2번은 이해를 했지만

입력 예3을 보고 당황했다

왜냐하면 입력은 두 자연수 A와 B를 이루는 1의 개수가 주어지는데,

 

1의 개수가 입력 예3만큼이면? 범위 초과다.

그래서 뭔가 숨겨져있는게 있겠지하고 고민했다.

 

입출력 예들을 자세히 보니까

먼저 입력으로 주어진 두 수의 최대공약수를 구하고,

최대 공약수가 즉 숫자의 길이가 되는 것이였다.

 

입출력 예 2를 보면

6과 3의 최대 공약수를 구하면 3이다.

그렇다면 숫자의 길이가 3이 되어야 한다.

그리고 숫자는 1로만 이루어져 있으므로, 결과는 111 이다. 

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <iostream>
#include <string>

using namespace std;

int gcd(unsigned long long a, unsigned long long b) {
    unsigned long long r = 0;
    while(true) {
        r = a % b;
        if(r == 0)
            break;
        a = b;
        b = r; 
    }

    return b;
}


int main(void) {
    unsigned long long a, b;
    cin >> a >> b;
    int len = 0;
    if (a > b) len = gcd(a, b);
    else len = gcd(b, a);

    string s;
    for(int i = 1; i <= len; ++i) {
        s += '1';
    }
    cout << s;
}