[C++] 14658 - 하늘에서 별똥별이 빗발친다 (골드 3)

1. 문제 설명

 

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

시험 끝나면 코테 매일 한 문제씩 풀려고 벼르고 있었는데, 뭔 놈의 과제랑 쪽지 시험이 계속해서 쏟아진다.

그래서 쪽지 시험 반 쯤 던지고 풀었는데, 이딴 게 골드 3

---

2. 아이디어

 

가장 처음 보자마자 별 하나씩 트램펄린 꼭짓점에 두고 4방향을 뒤지면 될 거라고 생각했다.

이걸 문제를 보자마자 떠올렸는데, 가장 최근에 공부한 게 탐욕법이라서 그런가.

그런데 상식적으로 점 여러 개 찍어놓고, 정사각형 안에 최대한 많이 담아보라고 하면 보통 정사각형을 점들의 꼭짓점에 먼저 가져다 대보니까 그랬을 수도

(정당성 증명을 한다면 별들이 있을 때, 꼭짓점에 별이 존재하지 않는 최적해가 존재한다는 가정의 모순을 찾으면 된다. 생각해보면 이 때 반례를 찾았어야 했는데, 난 아직도 멀었다.)

 

그래서 처음에 이런 식으로 2중 반복으로 별들을 순회하면서, 4방향을 돌려보는 코드를 작성했다.

문제는 코드를 전부 작성하고 테스트를 통과하는데 고작 13분밖에 소모되지 않았다는 것.

 

이럴 리가 없다.

아무리 그래도 골드 3인데, 이렇게까지 단순할 리가 없다.

 

그래서 이번에는 별을 찍고 사각형을 대보는 것이 아니라, 사각형을 그리고 별을 배치하는 방식으로 접근해봤다.

아니나 다를까, 반례가 존재했는데 위와 같은 경우에는 이전의 방식으로 해를 구할 수 없다.

그렇다면 점을 4개씩 찍고 무게 중심을 구해야 하나 싶었는데, 할 수는 있지만 너무 귀찮았다.

 

그래서 꼼수를 쓴 게, 랜덤으로 별 두 개를 찍어서 오른쪽, 아래쪽을 뒤져보는 방법이었다. 

첫 번째 케이스는 당연히 통과할 거고, 모서리에 별을 가져다 대는 경우도 확인해볼 수 있으므로 나쁘지 않은 아이디어였다.

문제는 이 엉뚱한 아이디어가 통과할 수 있을까라는 걱정 + 마찬가지로 4방향을 뒤져야 하지 않을까 싶었는데,

 

첫 번째 고민은 기도 메타로 돌렸고,

(마냥 기도는 아니었던 게, 어차피 필요한 경우는 다 찾고 있으므로 엉뚱한 케이스를 탐색해내는 경우만 존재하지 않으면 됐는데 어차피 많이 찾아내면 이득이므로 손해볼 일은 없었다.)

 

두 번째 고민에 대해서는 어차피 좌측 상단을 살펴봐야 할 일이 생긴다면(좌측 상단에 별이 존재할 경우), 좌측 상단의 별을 기준으로 탐색이 이루어질 것이므로, 굳이 살펴볼 이유가 없다는 것이다.

애초에 처음 4방향을 탐색한다는 아이디어는, 별 하나만을 기준으로 탐색하기 때문에 필요한 과정이었다.

지금은 별 2개씩 찍고 볼 것이므로 좌상단에 별이 존재하지 않으면 굳이 탐색할 필요가 없는 경우를 걸러낼 수 있다.

탐색해야 한다면? 좌상단의 별이 알아서 탐색할 것이다.

 

두 번째 증명이 매끄럽지 않은 이유는 솔직히 나도 통과할 줄 몰랐다.

당연히 한 번 틀릴 거라 생각하고 제출했는데, 100% 뜨길래 어이가 없었음

 

---

3. 코드

 

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

int n, m, l, k;
vector<pii> stars;

int countReflection();

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> l >> k;
    for (int i=0; i<k; ++i) {
        int y, x; cin >> y >> x;
        stars.push_back({y, x});
    }

    cout << countReflection() << "\n";
}

int countInRange(int y, int x) {
    int cnt = 0;
    
    for (auto &cur : stars) 
        if ((y <= cur.first && cur.first <= y+l) && (x <= cur.second && cur.second <= x+l))
            ++cnt;

    return cnt;
}

int countReflection() {
    int res = 0;

    for (int i = 0; i < k; ++i) for (int j = 0; j < k; ++j) {
        res = max(res, countInRange(stars[i].first, stars[j].second));
    }

    return k - res;
}