[백준 21412] Дробь (C#, C++) - soo:bak

문제 링크

21412번 - Дробь

설명

분자와 분모의 합이 n이고, 분자 < 분모인 기약분수들 중에서 값이 가장 큰 분수를 구하는 문제입니다.

접근법

분자 a와 분모 b는 a + b = n을 만족하므로, a < b인 a의 최댓값을 찾으면 됩니다.

따라서 a를 ⌊(n-1)/2⌋부터 1까지 내려가며 gcd(a, n - a) = 1인 첫 분자를 찾고, 분모는 n - a로 두면 됩니다.

---

Code

C#

using System;

class Program {
  static int Gcd(int x, int y) {
    while (y != 0) {
      var t = x % y;
      x = y;
      y = t;
    }
    return x;
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var a = (n - 1) / 2;
    while (a >= 1) {
      var b = n - a;
      if (Gcd(a, b) == 1) {
        Console.WriteLine($"{a} {b}");
        return;
      }
      a--;
    }
  }
}

C++

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

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

  int n; cin >> n;
  for (int a = (n - 1) / 2; a >= 1; a--) {
    int b = n - a;
    if (std::gcd(a, b) == 1) {
      cout << a << " " << b << "\n";
      break;
    }
  }

  return 0;
}