[백준] 링 - 3036번

문제설명

www.acmicpc.net/problem/3036

3036번: 링

 

기본아이디어

문제를 읽고 12 / 3 -> 4 / 1, 12 / 8 -> 3 / 2 로 바꿔주는 작업이 필요하다고 생각이 들었고, 그때 필요한 두 값을 나누는 값은 두 값의 최대공약수라는 점을 파악했다. 그래서 두 값을 매개변수로 최대공약수를 리턴해주는 함수를 만들어서 사용했다. 알고리즘은 유클리드 호제법을 기반해서 만들어졌다.

 

<유클리드 호제법 간단 요약>

결과는 성공!

구현코드

public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(input.readLine());
 
        int[] rings = new int[N];
        StringTokenizer str = new StringTokenizer(input.readLine());
        for(int i = 0; i < N; i++){
            rings[i] = Integer.parseInt(str.nextToken());
        }
        for(int i = 1; i < N; i++)
            makeBunSu(rings[0], rings[i]);
 
        System.out.println(output);
    }
    static void makeBunSu(int A, int B){
        int GCD = makeGCD(A, B);
        output.append((A/GCD) + "/" + (B/GCD) + "\n");
    }
    static int makeGCD(int A, int B){
        int a = Math.max(A, B);
        int b = Math.min(A, B);
        while(b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

 

정리, 기억할내용

1. 유클리드 호제법 ( 두 값의 최대공약수는 두 값중 큰 값을 작은 값으로 나눈 나머지와 작은 값의 최대공약수와 같다.)