백준 2609번 C/C++

2609번: 최대공약수와 최소공배수

최대공약수와 최소공배수 문제를 보았을 때, 내가 알던 식으로 소인수분해를 하며 풀면 안될 것 같다는 생각이 들었다. 그래서 찾아보게 된 것이 유클리드 호제법이다.

 

유클리드 호제법

유클리드 호제법을 통해 최대공약수를 구할 수 있는데, 이것에 대한 설명은 다음과 같다.

숫자가 a와 b가 있고, a를 b로 나눈 나머지를 r이라고 한다. (여기서 a ≥ b이고, r은 0≤ r < b인 정수)

a와 b의 최대 공약수를 (a,b)라고 하면, 다음이 성립한다.

(a, b) = (b, r)

예시로 1071과 1029에 대한 예시를 위와 같은 표현으로 적어보면,

(1071,1029) = (1029, 42) = (42, 21) = (21, 0) = 21 처럼 쓸 수 있다.

최소 공배수

최소공배수 = 두 자연수의 곱 / 최대공약수

 

이것들에 대한 정보만 알고 있다면 문제를 풀 수 있다.

 

첫 번째 풀이

#define _CRT_SECURE_NO_WARNINGS
#define TRUE 1
#include <cstdio>

int main()
{
	int a, b, temp;
	int x, y;
	scanf("%d %d", &a, &b);
	x = a;
	y = b;

	while(TRUE) {
		if (a % b != 0) {
			temp = a % b; //temp == 나머지가 들어감
			a = b;
			b = temp;
		}

		else {
			break;
		}
	}

	printf("%d\n", b); //최대공약수
	printf("%d", x * y / b); //최소공배수

	return 0;
}

이 풀이에서는 while의 탈출조건을 그렇게 생각하지 않았는데, 다음과 같은 코드로 수정하면 조금 더 깔끔하게 볼 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int main()
{
	int a, b, temp;
	int x, y;
	scanf("%d %d", &a, &b);
	
	x = a;
	y = b;

	while(b) {
		temp = a % b; //temp 변수에는 나머지가 들어감.
		a = b;
		b = temp; //b에 나머지가 0이 들어가면 최대공약수가 구해졌다는 의미이므로 while탈출
	}

	printf("%d\n", a); //최대공약수
	printf("%d", x * y / a); //최소공배수

	return 0;
}

이것이 수정한 코드이다. 앞으로 더 더 열심히해야지~~