[BOJ] 백준 #1850. 최대공약수 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1850

• 알고리즘 분류: 유클리드 호제법, 수학
• 난이도: Silver Ⅱ

💬 풀이

이 문제도 역시 순탄하게 풀릴 거라고 착각했던 문제.ㅎ 그래 벌써 이렇게 쉽게쉽게 풀릴 리가 있나 한번에 척척척 푸는 날이 오긴 오겠ㅈㅣ….? 갈길이멀구만 허허😂

코드 다 작성해놓고 예제입력 돌려봤더니, 역시나 마지막 엄청 큰 수 입력에서 막힘. 시간초과인듯.

왜안돼.하면서 보다보니까 예제출력이 다 1, 111, 11, … 이런 식. 아마 구하려는 최대공약수는 11111, 11, 1111, … 다 이렇게 생긴 놈인가보다. ㅇㅋ. 문제에서 정답은 천만 자리를 안 넘는다고 했으니까 1, 11, …, 11111111까지 배열에 저장해놓고 이중에서 최대공약수를 찾아보기로 한다. 삽질이었다. …

알고보니 이 문제는 “1로만 이루어진 숫자들의 최대 공약수는 결국 1의 개수들의 최대공약수 만큼을 1로 나열한 것이 된다”는 걸 알아야만 풀 수 있는 문제였다. 이런 문제 싫음-_-

✔ 유클리드 알고리즘

'유클리드 호제법'이라고 해서, 두 자연수의 최대공약수를 구하는 알고리즘이다.

두 개의 자연수 a, b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한다.

ex) GCD(24,16) ⇒ GCD(16,8) ⇒ GCD(8,0) ⇒ 최대공약수 = 8

https://coding-factory.tistory.com/599

그리고 마지막으로, 다시 한 번 ‘long long’에 유의한다.
문제 조건 중 2^63 정도까지의 입력은 절대 일반적인 자료형으로 해결할 수가 없다. 여기서 대충 눈치 깠어야 했을 듯

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

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

int main() {
	//freopen("input.txt", "rt", stdin);
	long long A, B;
	cin >> A >> B;

	long long gcd = GCD(A, B);
	for (long long i = 0; i < gcd; i++) {
		cout << 1;
	}
	return 0;
}

---

😱 시행착오 코드

혹시 몰라 남겨놓는 시행착오 코드(일부)이다.

‘long long’이면 다 될 줄 알았던 과거의 나..ㅋㅋ

" 이러면 안 된다. "

C++

  ...

	long long A, B;
	cin >> A >> B;
	long long a=0, b=0;
	while (A--) {
		a += pow(10, A);
	}
	while (B--) {
		b += pow(10, B);
	}

	long gcd = min(a, b); // 최대공약수 (greatest common divisor)
	for (long i = gcd; i >= 1; i--) {
		if ((a % i == 0) && (b % i == 0)) {
			gcd = i;
			break;
		}
	}
	cout << gcd << endl;

	return 0;
}