[백준/BOJ] 1934번 최소공배수 (C/C++)

백준 온라인 저지(BOJ) 1934번 최소공배수

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

1934번: 최소공배수

* 사용언어 : C언어, C++

 

1. 문제

T개의 test case에 대해 주어지는 A, B의 최소공배수를 출력

 

2. 풀이

유클리드 호제법을 사용하여 최대공약수(GCD)를 구한 후 최소공배수를 출력하게 했습니다.

(두 자연수의 곱 == 두 수의 최소공배수 * 최대공약수)

 

코드로 충분히 설명이 가능한 것 같아서 자세한 설명은 생략하였습니다.

개념에 대한 이해가 필요하다면 '유클리드 호제법'으로 검색해서 다른 글을 읽어보시길 바랍니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1934_최소공배수
1112KB	0ms
*/
#include <cstdio>

int t, a, b;

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int gcd(int a, int b) {
	int r = 1;
	while (r) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &a, &b);
		
		if (a < b) swap(&a, &b);
		printf("%d\n", a * b / gcd(a, b));
	}
	return 0;
}

* swap 기능을 main 내에서 직접 구현한다면 포인터를 사용하지 않아도 됩니다.