BOJ 15750 Teleportation

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

15750번: Teleportation

솔직히 딱 보고 도저히 감이 오지 않아서 BOJ 에서 제공하는 힌트를 살짝 봤다. 

힌트는 수학, 스위핑이였다.

생각보다 간단한 풀이였기에, 문제 난이도는 잊고 다시 접근해봤다.

몇개의 그래프를 그려보니 특정 구간 a->b 일 때, Teleport를 x 에 설치할 때 걸리는 거리 d는 b 에서 최소가 된다는 것을 알 수 있었다. b 지점에서 Teleport 가 1씩 멀어질 때 마다 d는 1씩 증가하여 d == | a - b | 가 될때 까지 증가한다.

a, b의 case를 나누어서 d == | a - b | 가 되는 지점을 구할 수 있다.  (case는 code 에서 확인 가능)
a->b 구간에서 teleport 좌표 x와 거리 d의 그래프 개형 다음과 같다.

케바케

 

여기서 부터 살짝 막막했었는데, 예전에 풀었던 KAKAO 문제 중 code review 및 upsolving 과정에서 구간에 대한 합을 swipping으로 훑고 지나갈 때, 구간 시작 지점에 +1, 구간 종료 지점에 -1을 하는 풀이가 있었다는 것이 기억났다. 

하지만, 해당 문제는 좌표가 -10^8 ~ 10^8 였기 때문에, 위의 방법을 그대로 적용하긴 어려웠다. 

좌표범위에 비해 point 개수는 sparse 하므로, map 을 쓰는 것은 어떨까 생각했다. 

여기에, 기존 Teleport 를 사용하지 않은 거리의 합에 그래프의 기울기를 활용하여 특정 구간에 대해 (기울기 합) * (x 축 변화량) 을 더해간다면, 특정 지점 x에 대해 teleport 를 설치할 때 걸리는 거리 d의 총 합을 구할 수 있을 것이라 생각했다. 거리가 줄어들 때 기울기는 +1 혹은 -1 이기 때문이다.

이를 코드로 작성하면 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

typedef unsigned long long ll;

using namespace std;

int n;
ll answer=0xffffffffffffffff, total;
vector<pair<int, int>> points;
map<int, int> delta;

int main(){

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> n;
    points.resize(n);
    for(int i=0;i<n;i++) {
        int a, b; cin >> a >> b;
        total += abs(a-b);

        /* 1) 0 <= b <= a
           2) a <= b <= 0 
           3) 0 <= a <= b && (b-a) < a
           4) b <= a <= 0 && abs(b-a) < a
        */
        if(abs(a) > abs(a-b)) continue;

        delta[b] += 2;
        if(b <= 0 && 0 <= a){
            delta[0] -= 1;
            delta[2*b] -= 1;
        }
        else if(a <= 0 && 0 <= b){
            delta[0] -= 1;
            delta[2*b] -= 1;
        }
        else if(0 <= a && a <= b){
            delta[2*a] -= 1;
            delta[2*b - 2*a] -= 1; //b + (b-2a)
        }
        else if(b <= a && a <= 0){
            delta[2*a] -= 1;
            delta[2*b - 2*a] -= 1;
        }
    }

    int beforex = -2000000000, totalDelta = 0;
    for(auto p : delta){
        int nowx = p.first, nowd = p.second;
        total += (ll)(nowx - beforex)*(ll)totalDelta;
        //cout << nowx << " " << totalDelta << " " << total << "\n";
        if(total < answer) answer = total;
        totalDelta += nowd;
        beforex = nowx;
    }

    cout << answer << "\n";
    return 0;
}

생각보다 코드가 간단해서 좀 당황스러웠다...

PS. 다른 사람들의 코드를 보니 전처리를 좀 더 확실하게 한다면, 느린 map을 쓰지 않고도 답을 구할 수 있었다.