[JAVA]백준 알고리즘 3036번 : 링

3036번: 링

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

풀이

링들이 돌아가는 횟수는 링의 반지름과 반비례하다.
예를 들면 반지름이 4인 링이 1바퀴 돌 때, 반지름이 2인 링은 2바퀴를, 반지름이 8인 링은 1 / 2바퀴를 돈다.

이것을 기약분수로 출력해야 하는 것이 문제인데, 최대공약수를 이용하면 어렵지 않다.

 

findG 함수는 최대공약수를 구하는 재귀함수이다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int firstRing = Integer.parseInt(st.nextToken());
        for(int i = 0; i < N - 1; i++) {
            int ring = Integer.parseInt(st.nextToken());
            int G = findG(firstRing, ring);
            sb.append(firstRing / G).append("/").append(ring / G).append("\n");
        }
        System.out.println(sb);
    }
    public static int findG(int a, int b) {
        int r = a % b;
        if(r == 0) return b;
        else return findG(b, r);
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!