/ BOJ

BOJ_3036_링_JAVA

문제 : 링

링크 : BOJ_3036_링

접근 방식

링의 회전 바퀴 차이로 비유하며 난해하게 설명했지만, 핵심은 1번 수를 기준으로 최대공약수를 구해서 각 수를 나눈 뒤 분수처럼 표현해주는 것이다.

풀이 방법

  1. 1번 수를 읽어와 저장한다.

  2. 나머지 수들과 1번 수의 최대공약수를 구한다.

  3. 1번수 / 최대공약수+’/’+ i번째 수 / 최대공약수 의 방식으로 출력한다.

소스 코드


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

// 각 수를 최대 공약수로 나누어서 분수 형태로 표현하면 된다.
public class BOJ_3036_링 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int[] arr = new int[N];
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int first = arr[0];
		for(int i=1;i<N;i++) {
			int gcd = getgcd(first,arr[i]);
			System.out.println(first/gcd+"/"+arr[i]/gcd);
		}
	}

	public static int getgcd(int A, int B) {

		while(B != 0) {
			int R = A%B;
			A = B;
			B = R;
		}
		return A;
	}
}