[백준 3036] - [수학 최대공약수] - 링 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/3036

---

이문제는 높은 정답률을 자랑한다.

그렇다는건 너무 쉽다는 거고 깊은 생각을 할 필요가 없는 문제다.

4
12 3 8 4

예제와 같이 12 3 8 4가 입력이 되고 첫번째 링인 12가 한바퀴 돌았을때 다른 링들은 볓바퀴 돌것이냐 라는 말이다. 

그럼 12와 각 링들의 최대 공약수를 구해서 나눠 주면 되겠구나 생각했다. 

최대공약수 나눈다면 자연스럽게 기약분수로 만들어 질것이다.

12와 3의 최대 공약수는 3 -> 12 / 3 + "/" +3 / 3 하면 4/1

12와 8의 최대 공약수는 4 -> 12 / 4 + "/" + 8/4 하면 3/2

12와 4의 최대 공약수는 4 -> 12 / 4 + "/" + 4/4 하면 3/1

다 구했다 아주 쉬운 문제였다. 

정답률이 높으니깐 자신있게 풀었다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int testCase = Integer.parseInt(br.readLine());
        
        int[] arr = new int[testCase];
        
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        
        arr[0] = Integer.parseInt(st.nextToken());
        for(int i=1; i < testCase; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            
            int gcd = getGCD(Math.max(arr[0], arr[i]), Math.min(arr[0], arr[i]));
            sb.append((arr[0]/gcd)+"/"+(arr[i]/gcd) + "\n");
        }
        System.out.println(sb.toString());
        
    }
    
    public static int getGCD(int a, int b) {
        while(b > 0) {
            int tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}