백준 3036 링 Java: 회전수 비율을 최대공약수로 약분하기

백준 3036 링 Java 풀이는 원의 둘레 비율을 기약분수로 출력하는 문제다. 처음 풀었을 때는 비교적 쉽게 최대공약수와 약분을 떠올렸고, 정수론 단계에서 한 문제만 더 남았다는 짧은 학습 기록도 함께 적어 두었다. 풀이 자체는 단순하지만 “회전수”가 왜 반지름의 비율이 되는지 식으로 확인해 두면 외운 공식에 기대지 않을 수 있다.

첫 번째 링이 한 바퀴 돌 때 다른 링은 몇 바퀴 도나

반지름이 R인 원의 둘레는 2πR이다. 첫 번째 링의 반지름을 R₀, 비교할 링의 반지름을 Rᵢ라고 하자.

첫 번째 링이 한 바퀴 돌며 이동한 거리는 2πR₀다. 두 링이 맞물려 미끄러지지 않는다면 비교할 링의 회전수는 이동한 거리를 자기 둘레로 나눈 값이다.

(2πR₀) / (2πRᵢ) = R₀ / Rᵢ

2π가 약분되므로 두 반지름의 비율만 남는다. 출력은 기약분수여야 하므로 분자와 분모를 두 수의 최대공약수로 나눈다.

g = gcd(R₀, Rᵢ)
R₀ / Rᵢ = (R₀ / g) / (Rᵢ / g)

최대공약수는 유클리드 호제법으로 구한다

두 양의 정수 a, b에 대해 다음 성질을 반복한다.

gcd(a, b) = gcd(b, a mod b)

나머지가 0이 되면 그때의 a가 최대공약수다. 반지름을 직접 여러 값으로 나눠 보는 방식보다 빠르고 구현도 짧다.

Java 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int firstRadius = Integer.parseInt(st.nextToken());
        StringBuilder answer = new StringBuilder();

        for (int i = 1; i < n; i++) {
            int radius = Integer.parseInt(st.nextToken());
            int divisor = gcd(firstRadius, radius);

            answer.append(firstRadius / divisor)
                    .append('/')
                    .append(radius / divisor)
                    .append('\n');
        }

        System.out.print(answer);
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }
}

예제로 확인하기

입력:

4
12 3 8 4

출력:

4/1
3/2
3/1

첫 번째 링의 반지름 12와 반지름 8의 비율은 12/8이다. 최대공약수 4로 나누면 3/2가 된다. 두 반지름이 같다면 1/1, 한쪽이 다른 쪽의 배수라면 분모 또는 분자가 1인 형태가 자연스럽게 나온다.

복잡도와 자료형

• 각 최대공약수 계산: O(log min(R₀, Rᵢ))
• 전체 시간 복잡도: O(N log Rmax)
• 추가 공간 복잡도: 출력 buffer를 제외하면 O(1)
• 자료형: 문제의 반지름 범위에서는 int로 충분하다.

분수의 분자·분모를 최대공약수로 줄이는 또 다른 예제는 백준 16430 제리와 톰, 큰 exponent를 절반씩 줄이는 정수론 예제는 백준 1629 곱셈에서 이어서 볼 수 있다.

참고 자료

• 백준 3036: 링
• Internet Archive: 백준 3036 문제 스냅샷
• NIST DADS: Euclid's algorithm