백준 문제풀이 : (2436) 공약수 - c/c++

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

2436번: 공약수

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	128 MB	Gold 5	수학 / 브루트포스

 

 

문제

 

 

풀이

최대공약수(G)와 최소공배수(L)이 주어졌을 때, 역으로 두 수 a, b를 구해야하는 문제다.

또한, a, b의 쌍이 여러개일 경우 a+b의 값이 최소가 되는 쌍을 찾아야 한다.

 

다 재쳐두고 먼저 G과 L에 대한 공식과 규칙들을 정리해봤다.

 

- G * L = a * b

- a = G * L / b (a와 b 반대일 경우에도 마찬가지)

- 1 <= G <= (a, b) <= L <= 100,000,000

- a와 b는 G의 배수이다.

- a와 b는 L의 약수이다.

 

더 뽑아볼 수 있겠지만 다 비슷한 내용일테고, 위 다섯 항목 정도로도 문제 풀이에는 충분할 것 같았다. 

 

시간 제한이 1초이므로 모든 숫자쌍을 검사하는 풀이는 불가능하다. 따라서 반복 횟수를 줄일 수 있는 방법을 찾아야 한다.

 

a와 b의 최솟값은 G이고, a와 b는 무조건 G의 배수이다. 따라서 반복문에서 a의 초기값을 G로 두고, 증가값을 G로 하여 숫자들을 검사해나가면 G가 1이더라도 최대 값인 100,000,000번 안에 계산이 가능할 것 같았다. 

 

a의 값을 G만큼 더해가며 검사하고 있으니, 매 반복 마다 b 또한 최대공약수&최소공배수 공식을 활용해 계산 가능하다.

 

 

코드 작성

#include <iostream>

using namespace std;

bool isRight (int g, int a, int b) { 
	// a, b 두 수의 최대공약수가 g가 맞는지 검증
    for (int i=g*2, j=3 ; i<=a ; i=g*j, j++) {  
        if (a%i==0 and b%i==0) return false;
    }
    
    return true;
}

int main() {
    long long G, L;
    scanf("%lld %lld", &G, &L);
    
    long long min = 200000001; //min이 될 수 있는 최댓값+1을 초기값으로.
    int resultA=0, resultB=0;
    
    for (long long a=G ; a<=L ; a+=G) {
        long long b = L*G/a;
        if (L%a==0 && L%b==0 && b%G==0) { //a와 b가 모두 L의 약수이며, G가 b의 약수이고, 
            if (isRight(G, a, b)) { //a와 b의 최소공배수가 G가 맞다면 정답.
                if (min>a+b) { //a+b가 가장 작은 값을 저장한다. 
                    min = a+b;
                    resultA=a;
                    resultB=b;
                }
            }
        }
    }
    
    printf("%d %d", resultA, resultB);
}

 

 

etc)

위 풀이에 써놓은 내용까지 생각하고 자신만만하게 코드를 작성했으나 반복 과정에서 한번 더 a, b 쌍이 올바른 지 검사하는 단계까 필요했다. 마땅한 방법이 생각나지 않아 'isRight' 함수를 새로 만들어 a, b의 최대공약수가 G가 맞는 지 체크했다. 

 

반복 횟수가 늘어난 것이기에 시간 초과를 우려했지만 다행스럽게도 무난하게 정답 처리를 받았다. 

 

 

END.