코딩 테스트/백준
[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;
}
결과
