[BOJ] 3036. 링 - JAVA

🔗 문제

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

3036번: 링

 

🧩 풀이 및 코드

문제 유형 : 정수론, 유클리드 호제법

 

유클리드 호제법

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

예시

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

 

(출처 : 

나머지 - 위키백과, 우리 모두의 백과사전

)

 

최대공약수를 구하는 자바 코드

 public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

 

 

전체 코드

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

public class Main_bj_3036_링 {

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input_bj_3036.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int first = Integer.parseInt(st.nextToken());
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<N; i++) {
			int next = Integer.parseInt(st.nextToken());
			
			// first 와 next 의 최대 공약수 구하기
			int res = gcd(first, next);
			sb.append(first/res).append("/").append(next/res).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}
	
	public static int gcd(int p, int q) {
		if(p%q == 0) return q;
		return gcd(q, p%q);
	}

}

 

---

Reference

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전