백준 2942번 퍼거슨과 사과 [최대공약수] :: 마이구미

이번 글은 백준 알고리즘 2942번 "퍼거슨과 사과" 를 다뤄본다.

문제 풀이는 GCD, 즉 최대공약수를 활용하여 문제를 해결할 수 있다.

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

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

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

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

본인은 문제는 쉬워보이나, 정답 비율이 높지 않아서 함정이 있을거라 생각했다.

틀릴거라 예상하고, 처음에는 단순히 브루트 포스를 이용하여 접근하였다.

선수 N을 하나씩 증가시키면서, R과 G를 N과 나머지 연산을 통해 0으로 떨어지는 경우를 걸러냈다.

while(true) {

    if (r < n || g < n) {
        break;
    }

    if (r % n == 0 && g % n == 0) {
        sb.append(n + " " + (r / n) + " " + (g / n) + "\n");
    }

    n++;
}

그 결과.... 정답.... 맞춰놓고도 당황했다.

하지만 다른 사람들과 비교하여 시간이 어마어마하게 걸렸다.

다른 풀이에서는 최대공약수를 이용한 것들을 볼 수 있다.

생각해보면, 두 수의 최대공약수까지 루프를 돌아도 무방하다.

또한, 최대공약수의 약수만 걸러내주면 된다는 것 또한 알 수 있다.

for (int n = 1; n <= gcd; n++) {

    if (gcd % n == 0) {
        sb.append(n + " " + (r / n) + " " + (g / n) + "\n");
    }

}

훨씬 속도를 개선할 수 있는 방법은 많다.

브루트 포스 방식에서 크게 소스 변화없이 최대공약수를 활용하여 속도 개선한 코드를 다뤄보았다.

백준 알고리즘 2942번 "퍼거슨과 사과" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/math/2942.java