[알고리즘] Java / 백준 / 링 / 3036

[알고리즘] Java / 백준 / 링 / 3036

문제

문제 링크

접근 방식

유클리드 호제법을 사용하여 첫번째 링과 i번째 링의 최대 공약수를 구한 후 각각을 나눠 기약분수꼴로 나타낸다.

코드

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

public class Main_3036 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int nums[] = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++){
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int firstRing = nums[0];
		for(int i=1;i<N;i++) {
			int gcd = euclid(firstRing,nums[i]);
			
			System.out.println(firstRing/gcd+"/"+nums[i]/gcd);
		}
		
	}
	
	
	
	public static int euclid(int a, int b) {
		
		if(b ==0)return a;
		return euclid(b,a%b);
	}
	

}