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

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

3036번: 링

 

 

 

 

---

- 문제

 

  링이 여러개 주어지면 첫 번째 링이 한 바퀴 돌 때 나머지 링들은 몇 바퀴 도는지 푸는 문제다.

 

 

---

- 해설

 

  두 번째 링이 첫 번째 링보다 크면 느리게 돌고

 

 두 번째 링이 첫 번째 링보다 작으면 빠르게 돈다는 것만 알고 기약 분수 형태로 만드는 방법을 알면 풀 수 있다.

 

 이 것도 유클리드 호제법으로 풀 수 있다.

 

 

 

---

- 풀이

#include <iostream>
using namespace std;

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

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

    int N, first, temp, tempgcd;

    cin >> N;
    cin >> first;
    for (int i = 0; i < N - 1; i++)
    {
        cin >> temp;
        tempgcd = gcd(first, temp);
        cout << first / tempgcd << '/' << temp / tempgcd << '\n';
    }

    return 0;
}

 

---

- 새롭게 알게 된 점