백준 2609번 [최대공약수와 최소공배수](C++)-yes6686- 티스토리

백준 문제 풀이: 2609 [최대공약수와 최소공배수]

---

문제 링크: https://www.acmicpc.net/problem/2609

문제 설명:

두 자연수가 주어질 때, 두 수의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    // 최대공약수를 구하기 위한 범위 설정
    int len = (a > b) ? b : a;

    int maxGCD = 1;
    for (int i = 1; i <= len; i++) {
        if (a % i == 0 && b % i == 0) {
            maxGCD = i;
        }
    }

    // 최소공배수 계산: (a * b) / 최대공약수
    cout << maxGCD << endl;
    cout << (a * b) / maxGCD << endl;

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 최대공약수는 두 수를 나누어 떨어뜨릴 수 있는 가장 큰 수를 의미하며, 최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.
• 구현 세부사항:
  • 작은 값까지만 반복문을 돌며 공약수를 찾습니다.
  • 최대공약수(GCD)를 구한 후, 이를 사용해 최소공배수(LCM)를 계산합니다.
• 시간 복잡도: O(n), 여기서 n은 두 수 중 작은 값

---

결과

주어진 두 자연수의 최대공약수와 최소공배수를 출력합니다. 코드에서 반복문으로 최대공약수를 계산했으며, 이 값으로 최소공배수를 구했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!