백준 21920번 C++ 풀이

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

21920번: 서로소 평균

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	실버 4

 

문제

효성이는 길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구해보려고 한다.

효성이를 도와 이를 계산해주자.

입력

첫 번째 줄에 입력될 수들의 개수 N이 주어진다. (2 ≤ N ≤ 500,000)

두 번째 줄에는 수열 A를 이루는 자연수 Ai 가 공백으로 구분되어 주어진다. (2 ≤ Ai ≤ 1,000,000)

수열 A에 X와 서로소인 수가 최소 1개 이상 존재한다.

마지막 줄에는 X가 주어진다. (2 ≤ X ≤ 1,000,000)

출력

첫째 줄에 수열 A에서 X와 서로소인 수들의 평균을 출력한다.

절대/상대 오차는 1e-6까지 허용한다.

 

---

두 자연수 a, b가 서로소이려면 a와 b의 최대공약수, 그러니까 gcd(a,b)가 1이어야 한다. 그리고 일일이 숫자를 나눠보는 방식으로 최대공약수를 구한다면, O(min(a, b))의 시간복잡도를 가지게 된다. 문제는 이를 N번 수행해야하고, a, b의 최댓값이 50만이다. 이런 방식으로 문제에 접근하면 시간 복잡도는 O(N * min(a, b))가 되고, 극한의 케이스라면 50만(N 최대) * 100만(min(a, b)의 최댓값)이 되고, 이는 시간 제한을 한참 넘어서게 된다. 따라서 우리는 다른 방식을 찾아야 한다.

 

최대공약수를 빠르게 찾는 알고리즘은 유클리드 호제법이 가장 유명하다(사실 내가 이거밖에 모르긴 한다 ㅎㅎ;;). 두 자연수 A, B의 최대공약수를 찾을 때, 유클리드 호제법의 시간 복잡도는 O(max(logA, logB))가 된다.로그형태의 시간복잡도를 가지는 이 알고리즘은, 전에 서술한(일일이 나눠보는) 알고리즘의 시간복잡도인 선형복잡도보다 훨씬 빠르다. 따라서 우리는 이 알고리즘을 사용하면 될 것이다. 이 알고리즘에 대한 설명은 내가 하는거보다 다른 사람들이 훨씬 잘 설명했으니 구글링을 해보자.

 

풀이를 하면서 이상했던 점은 평균을 구할 때였다. 알고리즘도 다 맞았는데, 자꾸 틀렸다. 비슷한 상황을 겪은 사람이 있었고, 서로소인 값들의 합과 개수를 정수가 아닌 실수로 저장했더니 맞았다고 한다. 정수로 저장한 후, 실수로 형변환을 하면 틀렸다고 나온 것이다. 이유는 아직 모르겠다. 부동소수점때문에 틀린게 아닐까 하는 생각만 하고 있다. 이유를 알고 있다면 댓글로 정보공유 부탁드립니다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, x;
vector<int> A;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void input() {
    cin >> n;
    A.resize(n);
    for (int& an : A) cin >> an;
    cin >> x;
}

void sol() {
    double total = 0;
    double cnt = 0;

    for(int an : A) {
        if (gcd(an, x) == 1) {
            cnt++;
            total += an;
        }
    }

    cout.precision(7);
    cout << (double)total / cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}