[BOJ] 3036 - 링 (Java)

알고리즘

• 수학
• 정수론
• 유클리드 호제법

1. 문제

2. Idea

• 첫 번째 링을 기준으로 나머지 링들의 비율을 구하면 된다.

3. 풀이

3.1. 입력

• N: 링의 개수

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

3.2. 첫 번째 링 크기 저장

• first: 첫 번째 링의 크기

int first = Integer.parseInt(st.nextToken());

3.3. 나머지 링들과의 비율 계산 및 출력

• 첫 번째 링을 제외한 나머지 링들에 대해 반복문을 돌면서 각 링의 크기를 other에 저장
• first와 other의 최대공약수(GCD)를 계산
• 기약분수 형태로 출력하기 위해 first와 other을 각각 최대공약수로 나누고, 분자와 분모 출력

for (int i = 1; i < N; i++) {
    int other = Integer.parseInt(st.nextToken());
    int gcd = gcd(first, other);

    System.out.println((first / gcd) + "/" + (other / gcd));
}

3.4. 최대공약수(GCD) 계산 메소드

• 유클리드 호제법을 이용하여 두 숫자 a와 b의 최대공약수를 계산
• a를 b로 나눈 나머지를 r에 저장하고, a를 b로, b를 r로 갱신하는 과정을 반복
• b가 0이 되면 그 때의 a가 최대공약수인 것

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

4. 전체코드

import java.io.*;
import java.util.*;
 
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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		int first = Integer.parseInt(st.nextToken());
 
		for (int i = 1; i < N; i++) {
			int other = Integer.parseInt(st.nextToken());
			int gcd = gcd(first, other);
 
			System.out.println((first / gcd) + "/" + (other / gcd));
		}
	}
 
	// 최대공약수 메소드
	static int gcd(int a, int b) {
		int r;
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}