[C/C++] 백준 - 14658번 : 하늘에서 별똥별이 빗발친다

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

14658번: 하늘에서 별똥별이 빗발친다

문제

“오빠! 나 얼마만큼 사랑해?”

“널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?”

“에이, 거짓말!”

“정말이야. 한 번 봐봐!”

욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.

“자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.”

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

입력

첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 뜻한다. 이후 K개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 (x, y)가 주어진다. (0 ≤ x ≤ N, 0 ≤ y ≤ M)

출력

욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.

 

---

 

하늘에서 내리는 별똥별을 L*L 사이즈의 트램펄린으로 최대한 많이 튕겨내야한다. 즉, L*L 사이즈로 덮었을 때  별똥별의 위치를 최대 몇 개 덮을 수 있는지 알아내야한다.

 

브루트-포스 알고리즘이라하더라도 N과 M의 제한이 500,000이므로 이를 위치 하나 하나 옮겨가며 확인하는 방법은 비효율적이다.

그렇다면 다른 방법을 적용하여 문제를 해결해야한다.

 

트램펄린을 어디에 설치할지 고민해보면 트램펄린의 가장자리를 별똥별이 떨어지는 위치로 설치하여 확인해주어야 한다는 것을 감각적으로 떠올릴 수 있다. 그래야 공간을 최대한으로 활용할 수 있기 때문이다. 

 

트램펄린을 모든 위치에 설치하여 확인하는 방식이 아닌, 별똥별의 위치를 트램펄린 가장자리에 설치하여 모든 별똥별의 위치를 기준으로 트램펄린을 설치하는 방식으로 진행하는 것이다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, M, L, K;
vector<pair<int, int>> pos;

void input(){
    cin >> N >> M >> L >> K;
    for(int i=0;i<K;i++){
        int y, x;
        cin >> y >> x;
        pos.push_back({y, x});
    }
}

int calc(int y, int x){
    int cnt = 0;
    for(auto &cur : pos){
        if(y <= cur.first && cur.first <= y+L && x <= cur.second && cur.second <= x+L){
            cnt++;
        }
    }
    return cnt;
}

int solution(){
    int answer = 0;
    for(int i=0;i<K;i++){
        for(int j=0;j<K;j++){
            answer = max(answer, calc(pos[i].first, pos[j].second));
        }
    }
    return K-answer;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}