[백준] 2942번 퍼거슨과 사과

2942번 퍼거슨과 사과

문제

---

맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다.

예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다

선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다

선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다

선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.

퍼거슨이 사과를 나누어 주는 방법을 구하는 프로그램을 작성하시오. 훈련장에 선수는 무한히 많다.

입력

---

첫째 줄에 R과 G가 주어진다. (1 ≤ R, G ≤ 1,000,000,000)

출력

---

퍼거슨이 사과를 나누어 주는 방법을 출력한다. 방법을 출력할 때는 사과를 받게되는 선수의 수 N과 나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력한다.

각 방법은 한 번만 출력해야 한다. 나누어 주는 방법은 아무 순서로 출력해도 된다.

---

풀이)

R, G의 범위가 1,000,000,000 이여서 1부터 min(R,G)까지 나눌 수 있는 모든 수를 확인하면 시간초과가 난다.

최대공약수(greatest common divisor, gcd)를 구한 뒤 최대공약수의 약수를 이용해서 풀어야 한다. 

최대공약수는 유클리드 호제법 사용해서 구했다.

---

유클리드 호제법 (참조. 위키백과)

192와 72의 최대공약수를 이번에는 호제법으로 구하는 법. 

일단 192을 72로 나누어 나머지를 구한다.

$${\displaystyle 192=72\times 2+48}

이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.

$${\displaystyle 72=48\times 1+24}

이와 같은 연산을 나머지가 0이 될 때까지 반복한다.

$${\displaystyle 48=24\times 2+0}

나머지가 0이 되었으므로 연산을 중지한다. 

이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다. 24가 최대공약수

---

최대공약수의 약수는 1~gcd까지 나눠보는 법도 있지만 이는 시간이 오래 걸리므로 1~gcd의 제곱근까지 나눠보는 법 사용.

---

제곱근까지 나눠보는 이유

36의 약수를 구할 시. 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다

이는 1*36 = 2*18 = 3*12 = 4*9 = 6*6 임을 알 수 있다. 

제곱근을 기준으로 양쪽의 값 하나씩 곱했을때 36이 된다. 

제곱근보다 큰 약수는 이미 제곱근보다 작은 약수에서 구할 수 있기 때문에 제곱근까지만 비교해 주면 된다. 

코드)

#include <stdio.h>
using namespace std;
 
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
int main() {
 
    int R, G;
    scanf("%d %d", &R, &G);
 
    //최대공약수 찾고, 최대공약수들의 약수를 찾는 방법
    int val, temp;
    if (R < G) val = gcd(G, R);
    else val = gcd(R, G);
    
    for (int i = 1; i*i <= val; i++) {
        if (val % i == 0) {
            printf("%d %d %d\n", i, R / i, G / i);
            if (i != val / i) { //i가 제곱근이 아닐경우
                temp = val / i;
                printf("%d %d %d\n", temp, R / temp, G / temp);
            }
        }
    }
 
    return 0;
}