[BOJ/백준] 2609 최대공약수와 최소공배수

● [문제번호 2609] 최대공약수와 최소공배수

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

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

 

● 알아야 할 것

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

 

● 풀이 과정

: 최대공약수는 두 수 중에서 작은 수부터 공약수가 될 때까지 작아지며 확인한다.

: 최소공배수는 최대공약수를 먼저 구한 다음 (두 수의 곱) / 최대공약수 = 최소공배수 라는 식을 이용한다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

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

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int X, Y;

// 최대공약수
int GCD()
{
    // 두 수 중에 1개라도 1인 경우 최대공약수는 1이다
    if(X == 1 || Y == 1)
        return 1;
    
    // 두 수 중 작은 수부터
    int gcd = min(X, Y);
    // 공약수가 될 때까지 작아진다
    while(X % gcd != 0 || Y % gcd != 0)
        gcd--;
    
    // 공약수가 된 순간의 수가 최대공약수이다
    return gcd;
}

// 최소공배수
int LCM(int gcd)
{
    // (두 수의 곱) / 최대공약수 = 최소공배수
    return X * Y / gcd;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> X >> Y;
    
    // 최대공약수 함수 호출
    cout << GCD() << "\n";
    // 최소공배수 함수 호출
    cout << LCM(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