코딩 테스트/백준

[Baekjoon/백준] 2609번: 최대공약수와 최소공배수(C/C++)

JongHoon 2022. 3. 20. 21:51

단계별로 풀어보기 17단계(정수론 및 조합론) 3번 문제

https://www.acmicpc.net/step/18

 

정수론 및 조합론 단계

N개의 물건 중 순서를 고려하지 않고 K개를 고르는 경우의 수, 이항 계수를 구하는 문제

www.acmicpc.net


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

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

 

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

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net


문제 설명

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.


입력과 출력

입력: 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력: 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.


접근 방법

이번 문제는 두개의 자연수를 입력 받아 두 수의 최대 공약수와 최소 공배수를 출력하는 문제다.

일단 최대 공약수는 유클리드 호제법을 이용해서 해결한다. 단순하게 생각하면 큰 숫자를 작은 숫자로 나눈 나머지가 0이 나올때까지 계속 반복한다고 생각하면 된다. 최소 공배수는 '최대 공약수 * 최소 공배수 = 두 수의 곱'과 같으므로, '최소 공배수 = 두 수의 곱 / 최대 공약수'가 된다. 이를 이용해서 문제를 풀면 해결할 수 있다.

유클리드 호제법 설명은 이 블로그에 있는 그림을 보면 더 이해하기 편할 것 같다. 유클리드 호제법을 몰라서 이번 문제는 해당 블로그의 글을 보고 해결했다.


코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[]) {
	int A, B;

	cin >> A >> B;

	int tempA = A, tempB = B, C = A % B;
	while (C != 0) {
		tempA = tempB;
		tempB = C;
		C = tempA % tempB;
	}
	int GCD = tempB;	//GCD = Greatest Common Divisor(최대 공약수)

	int LCM = (A * B) / GCD;	//LCM = Least Common Multiple(최소 공배수)

	cout << GCD << endl;
	cout << LCM << endl;

	return 0;
}

결과

백준 제출 결과