[BOJ/백준] 1934 최소공배수

● [문제번호 1934] 최소공배수

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

1934번: 최소공배수

 

● 알아야 할 것

: 최소공배수와 최대공약수를 구하는 방법

 

● 풀이 과정

: 유클리드 호제법을 이용하여 시간단축을 해야하나 싶었는데 완전탐색으로 해도 시간초과가 나지 않았다.

: 최대공약수를 구한다음에 최소공배수를 계산하여 출력

 

● 주의 할 것

: NULL

 

● 참고 할 것

: 최대공약수, 최소공배수에 대한 수학적 이해 https://dimenchoi.tistory.com/46

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int T, A, B;

// 최소공배수를 구하는 함수
int GCD()
{
    if(A == 1 || B == 1)
        return 1;
    
    // 두 수 중에 작은 수를 선택
    int s = min(A, B);
    
    // 공약수가 될 때 까지 작아짐
    while(A % s != 0 || B % s != 0)
        s--;
    
    // 최초의 공약수가 최대공약수이다
    return s;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    for(int t = 0; t < T; t++)
    {
        cin >> A >> B;
        
        // 최대공약수를 구해서 최소공배수를 계산한다
        cout << A * B / GCD() << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [300 - 수학 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10430	나머지	https://pirateturtle.tistory.com/180
2	2609	최대공약수와 최소공배수	https://pirateturtle.tistory.com/181
3	1934	최소공배수	https://pirateturtle.tistory.com/182
4	1978	소수 찾기	https://pirateturtle.tistory.com/183
5	1929	소수 구하기	https://pirateturtle.tistory.com/184
6	6588	골드바흐의 추측	https://pirateturtle.tistory.com/185
7	10872	팩토리얼	https://pirateturtle.tistory.com/186
8	1676	팩토리얼 0의 개수	https://pirateturtle.tistory.com/187
9	2004	조합 0의 개수	https://pirateturtle.tistory.com/188