[Beakjoon Online Judge] 1850 - 최대공약수(C++)

문제

모든 자리가 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 6을 입력받는데 6보다도 큰 111을 출력한다고? 문제를 잘못봤었다.

 

• 2^63이면 int에는 못담고 long long을 써야하겠다 싶었고
• 그정도 큰 수는 최대공약수 구하면 무조건 시간초과일 것 같았고
• 1로 이루어진 특수한 수니까 규칙이 있을 것 같았다.

 

* 예시를 통한 규칙 추론

---

3 4 -> 1

3 6 -> 111

500000000000000000 500000000000000002 -> 11

이라는 입출력 예시를 보고 그냥 단순히 A와 B의 차이만큼 1을 출력하면 되는거 아냐? 싶었고

#include <iostream>
using namespace std;
int main(void)
{
	long long A,B,C,i;
	cin >> A >> B;
	if(A>B)
		C = A-B;
	else
		C = B-A;
	for(i=0;i<C;i++)
		cout << 1;
	return 0;
}

바로 코딩해서 제출해보았으나 택도 없었다.

생각해보니 1 6이 입력되면 1과 111111의 최대공약수는 당연히 1인데 11111이 출력되는게 말이 안되지 않은가?

 

그 조건까지 따져보았을 때 추론한 것이 A와 B의 최대공약수만큼 1을 출력하면 되는거 아냐? 싶었고

그렇게 코드를 짜보려고 하니 매우 큰 수의 최대공약수를 구한다는 것은 숫자를 하나하나 나눠지는지 비교하게 했다간 시간초과일 것 같았다.

 

그러다가 찾아낸 알고리즘이 [유클리드 알고리즘]이다.

 

유클리드 알고리즘의 핵심은 A>B일 때

A%B = n에서 n=0이면, B가 최대공약수이다.

n!=0이면, A의 자리에 B를 대입하고 B의 자리에 n을 대입한 후 다시 A%B(B%n)를 계산한다.

 

재귀적으로 돌아가면 최종적으로 최대공약수가 구해진다!

 

재귀로 작성한 유클리드 알고리즘 함수는 다음과 같다.

long long gcd(long long a, long long b){
    
    if(b == 0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}

 

그런데, 재귀로 할 경우 메모리를 초과할 가능성도 존재하기 때문에 반복문으로 작성해서 제출했다.

최종적인 답안은 다음과 같다.

#include <iostream>
using namespace std;
long long gcd(long long a, long long b)
{
	long long tmp, n;
	if(a<b)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	while(b!=0)
	{
		n = a%b;
		a = b;
		b = n;
	}
	return a;
}

int main(void)
{
	long long A,B,C,i;
	cin >> A >> B;
	C = gcd(A,B);
	
	for(i=0;i<C;i++)
		cout << 1;
	
	return 0;
}

 

혹시몰라서 재귀함수로도 제출해봤는데 신경쓸 필요 없이 맞았다. 맨 밑 출력초과는 처음에 그냥 쓴거고, 컴파일 에러는 오타가 있어서 났다 ㅎㅎ..

 

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1850번 최대공약수 C++

BOJ 1850번 최대공약수 C++

백준 1850번 최대공약수 C++