[백준 29196] 소수가 아닌 수 2 (C#, C++) - soo:bak

작성일 :

문제 링크

29196번 - 소수가 아닌 수 2

설명

문제의 목표는 소수 k 를 입력받아, k 의 근사치로 나타낼 수 있는 분수 p / q 를 찾는 것입니다.

이 때, k 와 p / q 의 절대오차 또는 상대오차는 10-6 이하여야 합니다.

풀이과정은 다음과 같습니다.

  • 문자열 처리 : 주어진 소수 k 에서 소수점 아래 부분만 추출합니다.

  • 비반복 소수와 반복 소수 구분 :

    • 비반복 소수와 반복 소수를 구분하는 것은 해당 소수를 분수로 변환할 때 사용할 방법이 다르기 때문입니다.

    • 비반복 소수 : 소수점 아래의 숫자가 반복되지 않는 경우, 예를들어 0.12 또는 0.12345 등

    • 반복 소수 : 소수점 아래의 숫자가 반복되는 경우, 예를 들어 0.3333... 또는 0.4646... 등

    • 반복 여부를 판단하는 방법으로, 간단하게 첫 번째 숫자와 마지막 숫자가 같은 경우를 반복 소수로 간주합니다.
      (절대오차 또는 상대오차 10-6 내에서 충분히 유효하게 판정할 수 있습니다.)

  • 분수 변환

    • 비반복 소수의 경우 : 소수점 아래 숫자를 분자로 사용하고, 분모는 해당 숫자의 길이에 따른 10 의 거듭제곱으로 설정합니다.

    • 반복 소수의 경우 : 분자는 소수점 아래의 숫자로 사용하고, 분모는 해당 숫자의 길이만큼 9 를 반복하여 설정합니다.
      이는 반복하는 소수의 특성을 이용한 것으로 0.3333... 을 해당 방법으로 분수로 표현하면 1 / 3 이 됩니다.

  • 최대공약수를 이용하여 기약분수로 변환 : 분자와 분모의 최대공약수를 구한 후, 분자와 분모를 최대 공약수로 나누어 기약분수 형태로 변환합니다.

  • 결과 출력 : 구한 분수를 출력합니다.

Code

[ C# ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

namespace Solution {
  class Program {

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

    static void Main(string[] args) {

      var k = Console.ReadLine()!;
      k = k[2..];

      int numerator, denominator;
      if (k.Length == 1 || k[0] != k[k.Length - 1]) {
        numerator = int.Parse(k);
        denominator = (int)Math.Pow(10, k.Length);
      } else {
        numerator = int.Parse(k);
        denominator = 0;
        for (int i = 0; i < k.Length; i++)
          denominator = (denominator * 10) + 9;
      }

      int commonDivisor = Gcd(numerator, denominator);
      numerator /= commonDivisor;
      denominator /= commonDivisor;

      Console.WriteLine("YES");
      Console.WriteLine($"{numerator} {denominator}");

    }
  }
}



[ C++ ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <bits/stdc++.h>

using namespace std;

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

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

  string k; cin >> k;

  k = k.substr(2);

  int numerator, denominator;
  if (k.length() == 1 || k[0] != k[k.length()-1]) {
    numerator = stoi(k);
    denominator = pow(10, k.length());
  } else {
    numerator = stoi(k);
    denominator = 0;
    for (size_t i = 0; i < k.length(); i++)
      denominator = (denominator * 10) + 9;
  }

  int commonDivisor = gcd(numerator, denominator);
  numerator /= commonDivisor;
  denominator /= commonDivisor;

  cout << "YES\n";
  cout << numerator << " " << denominator << "\n";

  return 0;
}

이 블로그의 다른 글