[백준] 3036 링

문제보기

기약분수 만드는건 여러가지 방법이 있는데, 분자분모의 약수를 각각 구해서 갯수를 차감하는 방식(숫자가 클 때)도 있고

그냥 분자, 분모 중 작은값을 출발로 해서 1씩 낮춰가며 약분해보는 방법도 있다 (숫자가 비교적 작을때 - 후자로 풀었음)

import java.util.*;
import java.io.*;

public class Main{
  // 기약분수를 반환하는 함수 
  static String kiyak(int a, int b){
    if( a == 1 || b == 1 ){ // 더이상 약분할게 없다
      return a + "/" + b;
    }
		// 분자가 분모보다 더 작은경우
    int rel = 0; // bunja : smaller
    int min = a;
    int max = b;
		// 분자가 더 큰 경우
    if( a > b ){
      min = b; max = a; rel = 1; // bunja : bigger
    }
		// 둘 중 작은 값부터 출발해 쭉 나눠본다 
    for(int i = min ; i >= 2 ; i-- ){
      if( min% i == 0 && max%i == 0 ){
        return rel == 0 ? (min/i) + "/" + (max/i) : (max/i) + "/" + (min/i);
      }
    }
		// 나눠진게 없다면 그대로 출력하자 
    return rel == 0 ? (min) + "/" + (max) : (max) + "/" + (min);

  }
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] ring = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 0 ; i < n ; i++){
      ring[i] = Integer.parseInt(st.nextToken());
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 1 ; i < n ; i++){
      sb.append(kiyak(ring[0], ring[i])+"\n");
    }
    System.out.println(sb);
  }
}