백준 2436번 [공약수](C++)-yes6686- 티스토리

백준 문제 풀이: 2436 [공약수]

---

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

문제 설명:

두 정수 a와 b가 주어질 때, a는 두 수의 최대공약수(GCD), b는 최소공배수(LCM)입니다. 이러한 조건을 만족하는 두 수를 찾고, 두 수를 출력합니다. 여러 쌍이 있을 경우 두 수의 합이 가장 작은 쌍을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(long long int a, long long int b) {
    return (a * b) / gcd(a, b);
}

int arr[100001];

int main() {
    int a, b;
    cin >> a >> b;
    int s = 0;

    // b의 약수 구하기
    for (int i = 1; i * i <= b; i++) {
        if (b % i == 0) {
            arr[s++] = i;
            arr[s++] = b / i;
        }
    }
    sort(arr, arr + s); // 약수를 정렬하여 순차적으로 탐색

    int firstNum = 100000001;
    int secondNum = 100000001;

    for (int i = 0; i < s; i++) {
        if (arr[i] % a != 0) continue; // 최대공약수 조건 체크
        for (int j = i; j < s; j++) {
            if (gcd(arr[i], arr[j]) == a && lcm(arr[i], arr[j]) == b) {
                if (firstNum + secondNum > arr[i] + arr[j]) {
                    firstNum = arr[i];
                    secondNum = arr[j];
                }
            }
        }
    }
    cout << firstNum << ' ' << secondNum;
}

---

코드 설명

• 핵심 알고리즘: 약수 탐색과 최대공약수, 최소공배수 조건을 활용한 완전 탐색입니다.
• 구현 세부사항:
  • b의 약수를 구하여 배열 arr에 저장합니다.
  • 이중 루프를 사용하여 두 약수의 조합 중 최대공약수와 최소공배수 조건을 만족하는 쌍을 찾습니다.
  • 조건을 만족하는 경우, 두 수의 합이 최소가 되는 조합을 저장합니다.
• 시간 복잡도: O(√b + k^2), 여기서 k는 약수의 개수입니다.
  • 약수 구하기: O(√b)
  • 이중 루프 탐색: O(k^2)

---

결과

최대공약수와 최소공배수 조건을 만족하는 두 수 중 합이 최소가 되는 쌍을 출력합니다. 입력 범위와 조건에 맞게 완전 탐색으로 문제를 해결했습니다.

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