백준 1643 쿠폰

1643번 쿠폰

확룔을 이용한 구현 문제이다. 출력을 구현하는 것 자체는 쉬웠는데 확률 공식을 찾는데 오래... 굉장히 오래 걸렸다. 공식은 이 사이트를 참고했다. 사이트의 공식을 분수와 분자를 각각 구하는 알고리즘으로 구현한 후 이를 형식에 맞추어 출력해주었다. 확률과 통계 문제는 역시나 어렵다...

#include <iostream>

using namespace std;

int N;

int len(int n) {
    int h = 0;
    while (n > 0) {
        h++;
        n /= 10;
    }

    return h;
}

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

    return findGcd(b, a % b);
}

void solution() {
    int j = N;
    int b = N;

    for (int i = 1; i < N; i++) {
        int tj = j * (N - i) + N * b;
        int tb = b * (N - i);

        int gcd = findGcd(tj, tb);

        j = tj / gcd;
        b = tb / gcd;
    }

    if (j % b == 0) {
        cout << j / b << endl;
    }
    else {
        int d = j / b;
        j %= b;

        for (int i = 0; i < len(d); i++) {
            cout << " ";
        }
        cout << " " << j << endl;
        cout << d << " ";
        for (int i = 0; i < len(b); i++) {
            cout << "-";
        }
        cout << endl;
        for (int i = 0; i < len(d); i++) {
            cout << " ";
        }
        cout << " " << b << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    while (1) {
        cin >> N;

        if (cin.eof()) break;

        solution();
    }

    return 0;
}