[BAEKJOON] 3036 링

링

문제 요약

• 알고리즘 분류: 유클리드 호제법
• 난이도: Silver4
• 문제내용:
  • 첫 번째 링과 그 뒤의 각 링의 비례 하는 회전 수를 기약 분수 형태로 표현해라.
• 사이트 주소: https://www.acmicpc.net/problem/3036

3036번: 링

문제 풀이

1. 문제 접근 방법

 이 문제는 회전의 비례를 구해야 한다. 예를 들어 A가 20 바퀴를 돌아가고 B가 12 바퀴 돌아 간다고 가정 한다면  A : B = 20 : 12 = 10 : 6 = 5 : 3 으로 표현 할수있다. 그래서 기약 분수를 구하기 위해서는 두 수의 최대공약수를 구해야 한다.

최대 공약수는 유클리드 호제법으로 풀면  처리 시간이 모든 경우의 수를 구하는 것보다 빠르다. 유클리드 호제법에 대한 내용은 아래의 사이트에서 보면 된다.

https://jih3508.tistory.com/13

유클리드 호제법(Euclidean algorithm)

   2. 문제 푸는 방법

 

1. 첫번째 숫자 외 그 뒤의 숫자들의 최대공약수를 구한다.
2. 첫번째 숫자와 각 숫자를 나눈다.

CODE

Python

import math

size = int(input())
numbers = list(map(int, input().split()))

basic_number = numbers[0]
for number in numbers[1:]:
    gcd = math.gcd(basic_number, number)
    print(str(basic_number // gcd) + "/" + str(number // gcd))

Java

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));
		int size = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] numbers = new int[size];
		for(int i = 0; i < size; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		
		int basic_number = numbers[0];
		for(int i = 1; i < size; i++) {
			int gcd = GCD(basic_number, numbers[i]);
			System.out.println((basic_number / gcd) + "/" + (numbers[i] / gcd));
		}
		
	}
	
	// 최대 공약수 구하는 함수
	public static int GCD(int x, int y) {
		int r;
		while(x % y != 0) {
			r = x % y;
			x = y;
			y = r;
		}
		
		return y;
	}			
}