백준 5376번 소수를 분수로

< 백준 5376번 소수를 분수로 - 마포 코딩박 >

사용한 알고리즘: 수학


 소수를 입력받으면 분수로 출력하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (수학)
 순환소수의 분수 변환을 간단히 적겠습니다.
 분자 : (정수+순환소수 끝까지) - (정수~순환하지 않는 부분까지)
 분모 : 순환소수 자리 수만큼 9 찍고 비순환 소수 자리 수만큼 0 추가
 예를들어 1.0(123) = 10123 - 10 / 9990 = 10113/9990 입니다.

(2) (코드 11~50)
 과정 (1) 의 규칙에 따라 분자, 분모를 만들어 줍니다.
 기약분수로 출력해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	int T;
	string ques;
	ll GCD(ll x, ll y){
	if(y==0) return x;
	return GCD(y, x%y);
	}
	// 비순환 소수는 순환소수 앞에만 나올 수 있다.
	void makeans(string A){
	int SS = A.size();
	// 분자
	ll BoonJa = 0LL;
	// 앞에 두개는 '0.' 이므로 3번째부터 봄
	int idx = 2;
	while(1){
	if(idx==SS) break;
	if(A[idx]=='(') break;
	BoonJa = BoonJa*10+(A[idx]-'0');
	idx++;
	}
	// 비순환 소수 자리수
	int cnt = idx-2;
	// 순환 소수 자리수
	int cnt2 = 0;
	//순환소수 있을때 A[idx] = '(' 상태
	if(idx!=SS){
	// temp2 = 비순환 소수
	ll temp2 = BoonJa;
	while(1){
	idx++;
	if(A[idx]==')') break;
	BoonJa = BoonJa*10+(A[idx]-'0');
	cnt2++;
	}
	// 전체 - 비순환소수
	if(BoonJa!=temp2) BoonJa -= temp2;
	}
	// 분모
	ll BoonMo = 0LL;
	//순환소수 자리 수만큼 분모에 9채우기
	while(cnt2--) BoonMo = BoonMo*10+9;
	if(BoonMo == 0LL) BoonMo = 1LL;
	// 비순환 소수 자리 수만큼 분모 뒤에 0 채우기
	while(cnt--) BoonMo*=10;
	ll G = GCD(BoonMo, BoonJa);
	cout << BoonJa/G << '/' << BoonMo/G << '\n';
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	cin >> ques;
	makeans(ques);
	}
	return 0;
	}

view raw BOJ 5376.cpp hosted with ❤ by GitHub