[파이썬/python] 백준 - 5376 소수를 분수로

문제

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

---

문제 설명

1. 유리수 분수를 소수로 나타내면 유한 소수와 무한 소수로 나타낼 수 있다.
2. 소수를 입력받은 뒤, 이를 분수로 나타내라

 

---

풀이

소수를 분수로 변환하는 과정은 중학생 때 배웠던 기억이 있다.

유한 소수라면 단순히 분자 / 분모를 하면 되지만, 무한 소수라면 말이 다르다.

 

예시를 들어보자.

0.333333...이라는 무한소수가 존재한다.

 

x = 0.333....이라고 가정하자.

그렇다면 10x = 3.333....이 될 것이다.

즉 10x - x = 3.333... - 0.333... = 3, 9x = 3, x = 1/3이다.

 

즉 무한소수를 분수로 변환하는 방법은 무한으로 되풀이 되는 부분을 제거하면 된다.

따라서 무한으로 반복되는 부분의 소수의 첫 자리까지 오도록 10의 제곱수를 곱해준 후 연산을 진행하여 분수로 변환하면 된다.

 

1. 주어진 소수를 정수 부분과, 소수 부분으로 나누어 정리한다.
2. 만약 사이클이 존재한다면 필요한 만큼 $10**N$을 곱하여 연산한다.
3. 분모와 분자의 최대공약수를 구해 분모 분자가 서로소인 분수를 출력한다.

---

코드

import sys
from math import gcd
input = sys.stdin.readline

for tc in range(int(input())):
    dcm = list(input().strip())
    front = ['0']
    front_cnt = 0
    for i in range(2,len(dcm)):
        if dcm[i] == '(':
            cycle = ''.join(dcm[i+1:-1])
            break
        front.append(dcm[i])
        front_cnt += 1
    else:
        a = int(''.join(front))
        b = 10**front_cnt
        c = gcd(a,b)
        print(f'{a//c}/{b//c}')
        continue

    a = int(''.join(front) + cycle)- int(''.join(front))
    b = int('9'*len(cycle)+'0'*front_cnt)
    c = gcd(a, b)
    print(f'{a//c}/{b//c}')

 

---

시간복잡도

• gcd의 시간복잡도는 $O(logN)$이다.
• 문제에서 주어진 N의 범위는 나와있지 않으며, 추론했을 때 약 $10**6$정도가 나올 수 있지 않을까 싶다.
• 따라서 약 $O(20)$ 정도의 시간으로 문제를 해결할 수 있다.