취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5376번 문제인 소수를 분수로이다.
문제는 아래 링크를 확인하자.

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

유한소수 또는 순환소수는 유리수이므로 항상 분모 분자가 정수인 분수의 형태로 바꿔 쓸 수 있다는 내용은 교과과정에 있다. 그리고 이를 계산하는 방법 또한 교과과정에 있다.

주어지는 소수 문자열이 0.A꼴이라면 이를 분수의 형태로 바꾸는 것은 매우 간단하다.

주어지는 소수 문자열이 0.A(B)꼴인 경우를 생각해보자.

먼저 A의 자릿수를 k, B의 자릿수를 l이라 하자.

이 때, 0.A는 A/(10^k)로, 0.(B)는 B/(10^l - 1)로 나타낼 수 있으므로, 0.A + 0.[k개의 0](B) = (B+A(10^l))/((10^k)(10^l - 1)) 으로 나타낼 수 있다.

분모와 분자가 서로소여야 한다는 조건이 있으므로 최대공약수를 구해 분모와 분자를 나눠주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

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

	int T; cin >> T;
	while (T--) {
		string s; cin >> s;
		int slen = s.length();
		int idx = slen;
		ll A = 0, k = 0, B = 0, l = 0;
		for (int i = 2; i < slen; i++) {
			if (s[i] == '(') {
				idx = i + 1;
				break;
			}
			A *= 10;
			A += s[i] - '0';
			k++;
		}
		for (; idx < slen; idx++) {
			if (s[idx] == ')') break;
			B *= 10;
			B += s[idx] - '0';
			l++;
		}
		ll k10 = 1, l10 = 1;
		while (k--) k10 *= 10;
		while (l--) l10 *= 10;

		ll ans1 = B + A * (l10 - 1), ans2 = k10 * (l10 - 1);
		if (ans2 == 0) ans1 = A, ans2 = k10;
		ll GCD = gcd(ans1, ans2);
		cout << ans1 / GCD << '/' << ans2 / GCD << '\n';
	}
}