[백준] 14658번: 하늘에서 별똥별이 빗발친다.

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

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

문제의 조건이 상당히 중요하다.

별똥별의 위치를 나타내는 좌표의 범위가 상당히 크다.(가로, 세로로 각각 50만..)

따라서 애초에 해당 좌표를 표시하는 2차원 배열을 쓸 생각을 버리고 시작해야 한다.

 

대신 별똥별의 개수가 최대 100개로 크지 않다.

따라서 별똥별을 일반 벡터에 있는 것으로 처리한다.

 

여기까지는 잘 풀었다.

하지만 그 다음이 문제였다. 어떻게 트램펄린을 배치해야할까...

 

처음에 떠올린 방법은 별똥별 위치를 각각 직사각형의 좌상단, 좌하단, 우상단, 우하단의 점으로 삼아 별똥별을 튕겨내는 개수를 세보려 했다. 하지만 이는 틀린 방식이었고, 반례가 존재한다.

          *

    *          *

         *

네 점을 한 트램펄린로 튕겨낼 수 있지만 위에서 언급한 방식으로는 접근 불가하다.

 

따라서 다른 접근 방식을 도입해야 한다.

효율적인 배치를 위해 각 두 점을 모서리에 걸쳐서 트램펄린을 배치할 수 있도록 하였다.

 

#include <iostream>
#include <vector>

using namespace std;
struct Star {
    int x, y;
};

int n, m, l, k, res;
vector<Star> arr;

void calc(int x, int y) {
    int cnt = 0;
    for(int i = 0;i < k;i++) {
        if(x <= arr[i].x && x + l >= arr[i].x && y <= arr[i].y && y + l >= arr[i].y) {
            cnt++;
        }
        res = max(res, cnt);
    }
}

int main(void) {
    cin >> n >> m >> l >> k;
    arr.resize(k);
    
    // 별들의 위치
    for(int i = 0;i < k;i++) {
        cin >> arr[i].x >> arr[i].y;
    }
    
    for(int i = 0;i < k;i++) {
        for(int j = 0;j < k;j++) {
            calc(arr[i].x, arr[j].y);
        }
    }
    
    cout << k - res;
}

 

참고

https://jaimemin.tistory.com/782

백준 14658번 하늘에서 별똥별이 빗발친다!!