[BOJ 14658] 하늘에서 별똥별이 빗발친다

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

 

 

2D 평면에서 고정 크기 사각형으로 최대 점 커버하기 문제다.

 

• 모든 좌표를 탐색하면 N, M <= 500,000 이므로 O(n^2)시 시간 초과가 난다.
• 어떤 좌표만 봐야할까?
  • 특이한 점만을 찾아 조져(?)야 된다고 판단.

별똥별이 트램펄린의 왼쪽 변 또는 아래 변에 딱 걸쳐 있는 경우만 조사해보자.

 

어떤 최적 위치가 있다고 하자:

┌─────────┐
│  ★   ★  │
│         │
│    ★    │
└─────────┘

이 트램펄린을 왼쪽으로 밀면?
→ 별이 빠져나가기 전까지는 커버 수가 그대로

그러다 별이 왼쪽 경계에 닿는 순간:
┌─────────┐
★    ★    │  ← 이 위치도 똑같이 최적이다.
│         │
│   ★     │
└─────────┘

 

for(int i=0; i<K; i++){           // 별똥별 i의 y좌표를 트램펄린 시작 y로
    for(int j=0; j<K; j++) {      // 별똥별 j의 x좌표를 트램펄린 시작 x로
        res = max(res, go(star[i].first, star[j].second));
    }
}

 

모든 (별똥별 y, 별똥별 x) 조합 -> K^2 개만 검사하면 된다.

 

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>

using namespace std;

int N, M, L, K, res;

// 별똥별 좌표
vector<pair<int, int>> star;

int go(int y, int x) {
    int cnt = 0;

    for(auto &cur: star) {
        if ((y <= cur.first && cur.first <= y + L)
            && (x <= cur.second && cur.second <= x + L)) {
            cnt++;        
        }
    }

    // cout << cnt << "\n";
    return cnt;
}

int main() {
    cin >> N >> M >> L >> K;

    for(int i=0;i<K;i++){
        int y, x;
        cin >> y >> x;
        star.push_back(make_pair(y, x));
    }

    for(int i=0;i<K;i++){
        for(int j=0;j<K;j++) {
            res = max(res, go(star[i].first, star[j].second));
        }
    }

    cout << K - res << "\n";
    return 0;
}