[백준/3036번] 링 (COCI 2006/2007)[Java]

문제

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

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

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

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

 

---

풀이

 

수학적 접근이 필요한 문제이다.

입력받는 n개의 원 중 첫 원을 circle로 저장하고 그 이후 토큰 부터 첫번째 circle과 비교하며 진행한다. 반지름에 따른 회전 수는 규칙을 보면 두개의 원 반지름의 최대공약수를 a/최대공약수(a,b) + "/" + b/최대공약수(a,b) 의 형태로 표현할 수 있다. 최대공약수 gcd 메소드를 만들고 이를 반복문에 적용해 준다.

 

import java.util.*;
import java.io.*;
 
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine()); // circle num
        
        StringTokenizer st= new StringTokenizer(br.readLine()); 
        int circle = Integer.parseInt(st.nextToken()); //first circle
        
        for(int i=0;i<n-1;i++) {
            int tmp = Integer.parseInt(st.nextToken()); //nextcircle
            System.out.println(circle/gcd(circle,tmp)+"/"+tmp/gcd(circle,tmp));
        }
    }
    public static int gcd(int a, int b) {
        while(b!=0) {
            int r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
}

 

https://www.acmicpc.net/problem/3036

3036번: 링