알고리즘/백준

[백준][C++] 3036: 링

KANTAM 2024. 1. 15. 20:45

문제

 

3036번: 링

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

www.acmicpc.net

풀이

유클리드 호제법

 

회전하는 바퀴는 반지름 / (첫 번째 링과 i 번째 링의 반지름의 gcd) 로 구할 수 있다. 

코드

#include <iostream>

using namespace std;

int nums[100];

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }

    for (int i = 1; i < N; ++i)
    {
        int temp = gcd(nums[0], nums[i]);

        cout << nums[0] / temp << "/" << nums[i] / temp << '\n';
    }

    return 0;
}