[ 백준 1850 ] 최대공약수 (c/c++)

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

 

 

[ 문제 요약 ]

두 숫자의 1의 개수가 주어질 때, 두 수의 최대공약수를 출력한다.

 

 

[ 문제 풀이 ]

1. 숫자가 1만으로 이루어져 있기 때문에 유클리드 호제법에 따라서 자리수의 gcd값이 두 수의 자리수, 즉 1의 개수가 된다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

long long a, b;

long long gcd(long long a, long long b){
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin >> a >> b;
    for (int i=0; i<gcd(a, b); i++) cout << 1;
    return 0;
}

 

 

[ 주의할 점 ]

유클리드 호제법에서 숫자가 1만 존재하는 경우에 생기는 특수한 경우이다.