[백준 - 9734] 순환 소수 - C++

분류: 수학, 유클리드 호제법, 문자열, 파싱 /

 

문제

문제 링크

문제 설명

분수는 소수로 바꿀 수 있다. 예를 들어, 12\(\frac{1}{2}\)는 0.5\(0.5\)이고, 13\(\frac{1}{3}\)은 0.333…\(0.333\dots \)이며, 간단하게 0.3―\(0.\overline { 3 } \)으로 쓴다. 0.5\(0.5\)는 길이가 유한하지만, 0.3―\(0.\overline { 3 } \)는 반복된다. 아래는 분수를 순환 소수로 나타낸 예시이다.

 27=0.285714―1766=0.2575―256=4.16―3401333=10.213―\[\frac{2}{7} = 0.\overline{285714} \\ \frac{17}{66} = 0.25\overline{75} \\ \frac {25}{6} = 4.1\overline{6} \\ \frac{3401}{333} = 10.\overline{213}\] 

순환 소수가 주어졌을 때, 분수로 바꾸는 프로그램을 작성하시오. 분자와 분모는 서로소이어야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 순환 소수 하나로 이루어져 있으며, 반복되는 부분은 괄호로 감싸져 있다. 각 소수에 있는 숫자의 개수는 최대 9개이다.

출력

입력으로 주어진 소수마다 분수를 출력한다. 분자와 분모는 서로소이어야 한다.

 

풀이

#include <iostream>
#include <string>
using namespace std;

inline void push(int &n, int a) { 
    n = 10*n + a; 
}
int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b, a%b);
}

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

    while(1) {
        string s; cin >> s;
        if(cin.eof()) break;

        int i=-1, n=0, u=0, d=0, nines=0, zeros=0;
        while(s[++i] != '.') {
            push(n, s[i] - '0');
            push(u, s[i] - '0');
        }
        while(s[++i] != '(') {
            push(n, s[i] - '0');
            push(u, s[i] - '0');
            zeros++;
        }
        while(s[++i] != ')') {
            push(n, s[i] - '0');
            nines++;
        }
        u = n-u;
        while(nines--) push(d, 9);
        while(zeros--) push(d, 0);

        int g = gcd(u,d);
        u /= g; d /= g;
        cout << s << " = " << u << " / " << d << '\n';
    }
}

문제 자체는 중학교 수학문제.

내가 풀었지만 `while(s[++i] != '.')`로 파싱한건 참 잘 짠 것 같다.

파싱하며 구간으로 슬라이싱할 때 자주 사용할 것 같다.

 

`n`: 소숫점과 괄호를 제외한 모든 숫자다.

`u`: 분자

`d`: 분모

혹은 다음과 같이 계산할 수도 있다.

#include <iostream>
#include <string>
using namespace std;

inline void push(int &n, int a) { 
    n = 10*n + a; 
}
int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b, a%b);
}

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

    while(1) {
        string s; cin >> s;
        if(cin.eof()) break;

        int i=-1, n=0, a=1, b=1;
        while(s[++i] != '.') {
            push(n, s[i] - '0');
        }
        while(s[++i] != '(') {
            push(n, s[i] - '0');
            a*=10;
        }
        while(s[++i] != ')') {
            push(n, s[i] - '0');
            b*=10;
        }
        int u = n - n/b, d = a*(b-1);
        int g = gcd(u,d);
        u /= g; d /= g;
        cout <<s<<" = "<<u<<" / "<<d<<'\n';
    }
}

`a`: 10^{(소숫점 아래 순환하지 않는 숫자의 갯수)}

`b`: 10^{(순환하는 숫자의 갯수)}