백준 14658번 하늘에서 별똥별이 빗발친다 (C++)

문제 링크 : https://www.acmicpc.net/problem/14658

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

 

문제 요약

 

1. n*m의 배열에는 k개의 별똥별이 떨어집니다. (1<=n,m<=500,000), (1<=k<=100)

2. l*l의 트램펄린이 주어집니다. (1<=l<=100,000)

트램펄린은 n*m배열 내부에 위치하며, 트램펄린을 비스듬하게 (대각선으로) 배치시킬 순 없습니다.

3. 트램펄린을 잘 배치하여 최대한 많은 별똥별을 튕겨낼겁니다.

모서리에 부딪친 별똥별도 튕겨낼 수 있습니다.

4. 별똥별을 튕겨내고 결과적으로 지구와 충돌한 별똥별의 갯수를 출력하세요.

 

핵심 포인트

 

배열의 크기가 500,000*500,000이 될 수 있으므로, 모든 배열을 탐색할 순 없습니다.

대신 별똥별의 갯수는 100개이므로, 100*100*100의 3중 for문을 돌려도 시간초과가 발생하지 않습니다.

 

문제 풀이

 

1. 전역변수로 필요한 변수들을 선언합니다. 그리고 별똥별의 갯수만큼 별똥별의 위치를 입력받습니다.

    int n,m,l,k; // n = 별똥뱔이 떨어지는 구역의 가로길이, m = 세로길이, l = 트램펄린의 한 변의 길이, k = 별똥별의 수
    cin >> n >> m >> l >> k;
    int y,x,ny,nx,ans=0,cnt=0;
    vector<pair<int,int>> v(k);
    for(int i=0; i<k; i++){
        cin >> x >> y;
        v[i] = {x,y};
    }

 

2. 별똥별의 갯수만큼 3중 for문을 돌립니다.

    for(int i=0; i<k; i++){
        for(int j=0; j<k; j++){ // 1
            cnt = 0;
            x = v[i].first;
            y = v[j].second;
            for(int a=0; a<k; a++){
                nx = v[a].first; // 2
                ny = v[a].second;
                if(x<=nx&&x+l>=nx&&y<=ny&&y+l>=ny) cnt++; // 3
            }
            ans = max(ans,cnt); // 4
        }
    }

(1) 이 2중 for문을 돌리면 두 별을 모서리로 튕겨낼 수 있는 트램펄린의 위치를 만들 수 있습니다.

쉽게 예시를 들면 다음과 같습니다.

예를 들어 한 점의 좌표가 (1,1), 다른 점의 좌표가 (5,5)이며, 트램펄린의 길이는 4*4일 경우

(1)번의 2중 for문을 돌렸을 때, 위와 같이 4개의 구역들에 한 번씩 트램펄린을 설치하게 됩니다.

때문에 (1,1)과 (5,5)를 모서리에 두고 (1,1), (5,5)에 위치한 각각의 별똥별을 튕겨낼 수 있는 기회를 갖게됩니다. 

(이해가 안될 경우, for문을 돌리는 경우를 직접 그려주면 도움이 됩니다.)

 

(2) 다시 한번 for문을 돌립니다. 이 for문을 통해 설치된 트램펄린에 튕겨내는 별똥별의 갯수를 구할 수 있습니다.

 

(3) 트램펄린 내부에 별똥별이 위치한다면 cnt를 +1해주면 됩니다.

 

(4) ans와 cnt중 최대값을 ans로 갱신합니다.

 

3. 문제에서 요구하는 정답은 튕겨낸 별똥별의 갯수가 아닌 지구에 충돌한 별똥별의 갯수이므로, k-ans를 출력합니다.

cout << k-ans << "\n";

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,l,k; // n = 별똥뱔이 떨어지는 구역의 가로길이, m = 세로길이, l = 트램펄린의 한 변의 길이, k = 별똥별의 수
    cin >> n >> m >> l >> k;
    int y,x,ny,nx,ans=0,cnt=0;
    vector<pair<int,int>> v(k);
    for(int i=0; i<k; i++){
        cin >> x >> y;
        v[i] = {x,y};
    }
    for(int i=0; i<k; i++){
        for(int j=0; j<k; j++){
            cnt = 0;
            x = v[i].first;
            y = v[j].second;
            for(int a=0; a<k; a++){
                nx = v[a].first;
                ny = v[a].second;
                if(x<=nx&&x+l>=nx&&y<=ny&&y+l>=ny) cnt++;
            }
            ans = max(ans,cnt);
        }
    }
    cout << k-ans << "\n";
    return 0;
}