3036. 링 (자바, Java)

맞물리는 톱니바퀴는 같은 시간동안 거리를 돈다. 하지만 톱니바퀴 크기에 따라 돌아가는 바퀴 수가 다를 뿐.

원리를 몰라도 눈치채신 분들도 있을것이다. 양쪽 숫자의 최대공약수로 나눠준 몫을 출력하면 된다.

첫 출력값에서 8과 4의 최대공약수는 4이므로, 각각 4로 나눠주면 2, 1이 되어 2/1이 되고,

8과 2의 최대공약수는 2이므로, 각각 2로 나눠주면 4, 1이 되어 4/1이 되는 식이다.

첫 바퀴가 한 바퀴를 도는동안 이동거리는 원의 반지름에 비례한다. (2 * r * pi 로, 정확하게 반지름은 아닌 비례관계)

따라서, 다른 바퀴가 그동안 이동거리도 똑같기 때문에, 바퀴수는 r2/r1이 된다. 이를 기약분수로 나타내려면, 양쪽을 최대공약수로 나눠주면 되는 것이다.

 

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

public class Main {

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

	}
	
	public static int gcf(int a, int b) {
		if (b==0) return a;
		return gcf(b, a%b);
	} // 최대공약수 구하는 매소드, a>b

}