Baekjoon 17877번 Integer Division

문제

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

걸린 시간

00 : 51 : 38

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
typedef long long ll;
using namespace std;

int n, d, a;
map<int, int> ad;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> d;
    for(int i = 0; i < n; i++){
        cin >> a;
        ad[a/d]++;
    }
    ll ans = 0;
    for(auto it = ad.begin(); it != ad.end(); it++){
        ll cnt = it->second;
        if(cnt > 0)
            ans += cnt*(cnt-1)/2;
    }
    cout << ans;
    return 0;
}

주어진 수들 중에서 d 로 나눈 정수부가 서로 같은 쌍의 개수를 찾는 문제이다.

조건 중 고른 두 수의 인덱스를 나타내는 i, j 는 0 <= i < j <= n 이므로 순열이 아닌 조합의 경우 수를 찾으면 된다. 정수부가 같은 원소들을 분류하고 각각 2개씩 고른 값들의 합이 답이다.

정수부의 개수는 원소 a 의 입력 범위가 10억이므로 배열 대신 map 을 사용해 저장했다.

_nC₂ 의 계산 과정에서 산술 오버플로가 일어날 수 있으므로 long long 자료형을 사용해야 한다.