[BOJ/14746] Closest Pair, c++

🔗 링크

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

14746번: Closest Pair

🤯 한줄 후기

수식써서 어려워 보이게 하기

🤷 문제

👩‍💻 풀이

ICPC 예선 대비 팀 스터디를 시작했다. 

2017 대전 인터넷 예선 A번 문제인 Closest Pair. 처음에 괜히 저런 수식 때문에 읽기 어려워보였는데 사실 알고보면 간단한 문제이다.

 

최근접쌍의 거리 (여기서 말하는 거리 d = | x1 - x2 | + | y1 - y2 |)를 구하고, 해당 거리인 최근접쌍의 개수를 구하는 문제이다.

c1, c2는 각각 x점 좌표의 집합 p, q의 y좌표이다. 

이제 문제에서 이미 알고있는 부분들을 빼면 우리가 구해야하는 부분이 작아 진다.

최근접쌍의 거리중 최소인 min_distance를 풀어보자.

min_distance = min(d(p', q')) = min(| x1 - x2 | + | c1 - c2 |)  -> x1 은 집합 p의 원소, x2는 집합 q의 원소

c1, c2는 우리가 알고있는 점이다. 따라서 결과적으로 min(| x1 - x2 |) 를 구하는 문제로 바뀌게 된다.

집합 p, q는 각각 최대 50만이다. 당연히 O(n^2)으로 완전탐색을 할 수는 없다.

 

머리를 굴려서 시간을 줄여보자. 집합 p의 원소 중 하나인 x가 있을 때, x - x2 가 가장 작아지려면 x2에는 어떤 수가 와야할까? 

x2는 x와 가장 차이가 없는 혹은 같은 숫자가 와야한다.

우리는 아주 빠르게 집합 q에서 x와 가장 근소한 차이를 보이는 좌표의 위치를 알아낼 수 있다. 이분탐색을 사용하면 된다.

c++에는 아주 친절히 upper_bound, lower_bound로 위치를 알려준다.

 

집합 q를 정렬한 후, 집합 p를 차례대로 돌면서 upper_bound 를 통해 p[i]보다 크거나 같은 집합 q의 원소를 찾아낸다.

찾은 후 해당 좌표보다 하나 더 작은 원소까지 비교하여 현재 p[i] - q[index] 가 더 작아지면 개수를 세는 식으로 구현했다.

약간의 예외 처리가 필요한데 upper_bound 인덱스가 0, size-1일 때 처리가 필요하고, q의 원소의 개수가 1개일 때도 처리가 필요하다. 

이 부분만 유의하면 AC를 받을 수 있다.

💻 코드

//AC
//BOJ 14746 Closest Pair
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define INF 1e9
vector<int> p;
vector<int> q;
int main() {
    int n, m, c1, c2, num;
    scanf("%d %d", &n, &m);
    scanf("%d %d", &c1, &c2);
    for(int i=0; i<n; i++) {
        scanf("%d", &num);
        p.push_back(num);
    }
    for(int i=0; i<m; i++) {
        scanf("%d", &num);
        q.push_back(num);
    }
    sort(q.begin(), q.end());
    int min_value = INF, cnt = 0, lower_value, upper_value;
    for(int i=0; i<n; i++){
        int value = p[i];
        int idx = upper_bound(q.begin(), q.end(), value) - q.begin();
        if(idx >= m) {
            idx -= 1;
        }
        upper_value = q[idx];
        if(m == 1) {
            if(abs(value - upper_value) < min_value) {
                cnt = 1;
                min_value = abs(value - upper_value);
            }
            else if(abs(value - upper_value) == min_value)     cnt += 1;
            continue;
        }
        if(idx == 0)    lower_value = q[idx+1];
        else    lower_value = q[idx - 1];
        int upsum_value = abs(value - upper_value);
        int losum_value = abs(value - lower_value);
        if(upsum_value == losum_value) {
           if(upsum_value == min_value) {
                cnt += 2;
            }
            else if (upsum_value < min_value) {
                min_value = upsum_value;
                cnt = 2;
            }
        }
        else {
            int min_sum_value = min(upsum_value, losum_value);
            if(min_sum_value == min_value) {
                cnt += 1;
            }
            else if(min_sum_value < min_value) {
                min_value = min_sum_value;
                cnt = 1;
            }
        }    
    }
    int ans = abs(c1 - c2) + min_value;
    printf("%d %d", ans, cnt);
    return 0;
}