[BOJ 3036] 링 (Java)

문제

https://www.acmicpc.net/problem/3036

3036번: 링

백준 3036번: 링

풀이

큰 링의 반지름과 나머지 링 반지름의 최대 공약수를 각각 구하여 나눈다.

유클리드 호제법을 사용한다.

 

소스코드

package math;

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

public class BOJ3036 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int first = Integer.parseInt(st.nextToken());
        for(int i = 1; i < N; i++){
            int ring = Integer.parseInt(st.nextToken());
            bw.write(getIrreducibleFraction(ring, first) + "\n");
        }
        bw.flush();
    }
    public static String getIrreducibleFraction(int num, int divisor){
        int gcd = getGCD(num, divisor);
        return divisor/gcd + "/" + num/gcd;
    }

    public static int getGCD(int a, int b){
        if(a < b){
           int temp = a;
           a = b;
           b = temp;
        }

        while(a%b != 0){
            int temp = a;
            a = b;
            b = temp%b;
        }
        return b;
    }
}