[Java] 백준 3036번 링

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

3036번: 링

문제 설명

• N개의 링이 접하도록 놓여있을때 첫번째 링을 한바퀴 돌리면 나머지 링이 몇바퀴 돌아가는지 구하기
• 반지름은 1~1000까지 자연수

최대공약수를 나누고 각각의 수를 최대공약수로 나누어 출력하는 간단한 수학적 개념의 문제이다.

최대 공약수를 구하는 코드는 다음과 같다.

public static int gcd(int a, int b){
		while(b!=0){
			int r = a%b;
			a= b;
			b= r;
		}
		return a;
	}

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		
		int N =s.nextInt(); //링의 개수
		int first = s.nextInt(); //첫 번째 링
		for(int i=0;i<N-1;i++) {
			int rad = s.nextInt();
			int gcd = gcd(first,rad);
			System.out.println(first/gcd+"/"+rad/gcd);
		}
		
		
	}
	public static int gcd(int a, int b){
		while(b!=0){
			int r = a%b;
			a= b;
			b= r;
		}
		return a;
	}
}