백준 1934번 최소공배수

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

 

아이디어:

1. 더 큰 수를 기준으로 삼고 배수를 구한다.

2. 큰 수의 배수 중에서 작은 수로 나눴을 때 나머지가 0이 나오는 첫 번째 수를 최소공배수로 구한다.

3. for 문의 반복자 시작점을 0이 아닌 1로 설정해서 결과가 항상 0이 나오는 상황을 방지한다.

 

// 1934

#include <iostream>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int t, a, b, m, max;

	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> a >> b;

		if (a > b) {
			for (int j = 1; (a * j) <= (a * b); j++) {
				m = a * j;
				if (m % b == 0) {
					max = m;
					break;
				}

			}
		}
		else {
			for (int j = 1; (b * j) <= (a * b); j++) {
				m = b * j;
				if (m % a == 0) {
					max = m;
					break;
				}

			}
		}

		cout << max << "\n";
	}

	return 0;
}

 

모범답안:

1. a * b = 최대공약수 GCD * 최소공배수 LCM

ex) 6 * 8 = 2 * 24 = 48

2. 최소공배수 LCM = (a * b) / GCD

3. GCD 최대공약수는 유클리드 호제법을 이용해서 구하기

4. 유클리드 호제법: [a, b] -> [b, a % b] -> [a % b, b % (a % b)] ... -> (1항) % (2항) = 0일 때의 1항이 최대공약수 

 

유클리드 호제법 코드

// 반복

int Euclidean(int a, int b) // a > b 일 때
{
    int r
    while(b != 0) {
      r = a % b;
      a = b;
      b = r;
    }
    return a;
}

// 재귀

int Euclidean_Recursive(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}

 

#include <iostream>
using namespace std;

// 최대공약수를 구하는 함수 (유클리드 호제법 이용)
int gcd(int a, int b) {
	int r = a % b;
	if (r == 0) {
		return b;
	}
	else {
		return gcd(b, r);
	}
	
}

int main() {
	int T;        // 테스트 케이스의 개수
	int A, B;
	int lcd;      // 최소공배수

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> A >> B;

		// 최소공배수 = (A x B) / 최대공약수
		lcd = (A * B) / (gcd(A, B));
		cout << lcd << "\n";
	}

	return 0;
}