[백준] 3036번 링 / C++ Java

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

C++

#include<iostream>
using namespace std;

int gcd(int a, int b) {
    if(a % b == 0) {
        return b;
    }
    return gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int arr1[101];
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    for(int j = 1; j < n; j++) {
        cout << arr1[0] / gcd(arr1[0],arr1[j]) << "/" << arr1[j] / gcd(arr1[0],arr1[j]) << endl;
    }
}

Java

import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {
        if(a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int [] radius = new int[N+1];
        int a = 0; int b = 0;
        for(int i = 0; i < N; i++) {
            radius[i] = scanner.nextInt();
        }
        for(int k = 1; k < N; k++) {
            a = radius[0] / gcd(radius[0], radius[k]);
            b = radius[k] / gcd(radius[0], radius[k]);
            System.out.println(a + "/" + b);
        }
        scanner.close();
    }
}

문제풀이

• 최대공약수를 사용해서 첫 번째 링의 반지름과 나머지 링의 반지름을 나눈 값을 기약분수로 나타내면 된다.

Comment

• 최대공약수를 구하는 유클리드 호제법만 알고 있으면 쉽게 문제를 풀 수 있다.