[백준 3036] 링 (C#, C++) - soo:bak

문제 링크

3036번 - 링

설명

여러 개의 링이 바닥에 나란히 놓여 있을 때, 첫 번째 링의 회전을 기준으로 나머지 링이 몇 바퀴 도는지를 기약 분수로 표현하는 문제입니다.

모든 링은 인접한 링과 맞닿아 있으며, 첫 번째 링이 한 바퀴 회전할 때, 각 링이 회전하는 횟수는 반지름의 비율에 따라 결정됩니다.

• 예를 들어 첫 링의 반지름이 8, 두 번째 링의 반지름이 4라면 두 번째 링은 첫 링보다 2배 더 빠르게 회전합니다.

이를 통해 첫 번째 링 기준 회전 횟수를 기약 분수 형태로 출력해야 합니다.

접근법

• 첫 번째 링의 반지름을 기준으로 각 링의 반지름과의 최대공약수(GCD)를 구합니다.
• 각 링의 회전 비율은 다음과 같은 수식으로 표현할 수 있습니다:

\[\frac{R_1}{\text{GCD}(R_1, R_i)} \bigg/ \frac{R_i}{\text{GCD}(R_1, R_i)} = \frac{R_1}{R_i}\]

• 다만 출력은 기약 분수 형태여야 하므로
  R1 / GCD : Ri / GCD를 각각 나누어 출력합니다.

참고 : GCD(최대공약수)와 유클리드 호제법의 원리 - soo:bak

참고 : 기약 분수(irreducible fraction)의 알고리듬적 접근 - soo:bak

---

Code

C#

using System;

class Program {
  static int Gcd(int a, int b) {
    return b == 0 ? a : Gcd(b, a % b);
  }

  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var tokens = Console.ReadLine().Split();
    int r1 = int.Parse(tokens[0]);

    for (int i = 1; i < n; i++) {
      int r2 = int.Parse(tokens[i]);
      int g = Gcd(r1, r2);
      Console.WriteLine($"{r1 / g}/{r2 / g}");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  vi radius(n);
  for (int i = 0; i < n; i++)
    cin >> radius[i];

  for (int i = 1; i < n; i++) {
    int gcd = getGcd(radius[0], radius[i]);
    cout << radius[0] / gcd << "/" << radius[i] / gcd << "\n";
  }

  return 0;
}