BOJ 2090 : 조화평균

• 문제 링크 : boj.kr/2090
• 난이도 : S4
• 태그 : 수학, 정수론

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

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

    int n;
    cin >> n;
    vector<ll> arr(n);
    ll mult = 1;
    for(auto &e : arr) {
        cin >> e;
        mult *= e;
    }

    ll msum = 0;
    for(auto e : arr) {
        msum += mult / e;
    }
    ll g = gcd(msum, mult);
    cout << mult/g << "/" << msum/g;

    return 0;
}

---

풀이

모든 값을 곱한 값을 M이라고 할때, 식을 정리하면 조화평균은 아래와 같다.

$${M} \over {\sum\limits_{i=1}^{n} {M \over a_i}}$$

$M \over a_i$는 정수이므로 분자와 분모가 두 정수 값으로 정해진다.

두 정수를 최대공약수로 나누어주면 된다.