110. 3036 링

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

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		ArrayList<Integer> ringList = new ArrayList<>();
		br.readLine();
		String[] sBits = br.readLine().split(" ");

		int ringFirst = Integer.parseInt(sBits[0]);
		for (int i = 1; i < sBits.length; i++) {
			ringList.add(Integer.parseInt(sBits[i]));
		}

		for (int val : ringList) {
			if (ringFirst % val == 0) {
				sb.append(ringFirst / val + "/1\n");
			}
			else {
				int ringGCD = GCD(ringFirst,val);
				sb.append(ringFirst/ringGCD + "/" + val/ringGCD + "\n");
			}
		}
		
		System.out.print(sb);

	}

	private static int GCD(int x, int y) {
		while (y != 0) {
			int r = x % y;
			x = y;
			y = r;
		}
		return x;
	}
}

문제요약

링 세개가 있는데 첫번째 링을 한 바퀴 돌리면 나머지 링은 몇 바퀴 도는가?

설명

문제는 크게 어렵지 않다.

for (int val : ringList) {
			if (ringFirst % val == 0) {
				sb.append(ringFirst / val + "/1\n");
			}

만약 회전한 바퀴가 정수로 떨어진다면 위와같이 작성할 수 있다.

ex)

8 4  |  첫 번째가 한 바퀴 돌 때 두번째 링은 두 바퀴를 논다 => 2 / 1

else {
				int ringGCD = GCD(ringFirst,val);
				sb.append(ringFirst/ringGCD + "/" + val/ringGCD + "\n");
			}

만약 정수로 떨어지지 않을 경우가 있다.

그 경우에는 두 수의 최대공약수를 구하고 그 공약수로 두 수를 각각 나누어주면 된다.

최대공약수는 유클리드 호제법을 사용하였다.

https://smhope.tistory.com/292

유클리드 호제법(최대공약수 구하기)

ex)

12 8  |  정수로 떨어지지 않음, 첫 번째가 한바퀴 돌때, 두 번째는 1.5바퀴 돈다. => 3 / 2 출력 필요

12와 8의 최대공약수는 4이다.

4를 각각 12와 8에 나누어 준다면 3 2가 나온다.