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

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

우선, N과 M이 최대 500,000이기 때문에 브루트 포스(Brute Force) 방식으로는 절대 풀 수 없는 문제입니다.

하지만 K는 최대 100이기 때문에 입력한 좌표를 통해서 풀 수 있을 것이라고 유추할 수 있습니다.

알고리즘은 아래와 같습니다.

1. [0 ~ K)까지 이중 반복문을 돌립니다.(i, j)

2. i번째 좌표를 정사각형의 좌상단 좌표로 지정하고 j번째 좌표를 정사각형의 우상단 좌표로 지정합니다.

3. 이제 [0~K)까지 반복문을 한번 더 돌리는데 2번에서 지정한 영역 내에 있는 좌표들의 개수를 구합니다.

4. 3번에서 구한 값 중 최대 값을 구합니다.

5. 4번에서 구한 값은 트램폴린에 들어가는 별똥별이기 때문에 지구에 부딪히는 별똥별은 (K - 4번에서 구한 값)입니다.

시간복잡도는 O(N^3)으로 꽤 커보이지만 K의 최대값이 100이기 때문에 시간 내에 풀 수 있다는 것을 유추할 수 있습니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100;

 

int N, M, L, K;

pair<int, int> coord[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M >> L >> K;

 

        for (int i = 0; i < K; i++)

                 cin >> coord[i].first >> coord[i].second;

 

        int result = 0;

        //i는 좌상단 

        for (int i = 0; i < K; i++)

        {

                 //j는 우상단 

                 for (int j = 0; j < K; j++)

                 {

                         int cnt = 0;

                         //좌표가 범위 내에 있는지 확인

                         for (int k = 0; k < K; k++)

                                 if (coord[i].first <= coord[k].first && coord[k].first <= coord[i].first + L && coord[j].second <= coord[k].second && coord[k].second <= coord[j].second + L)

                                          cnt++;

                         result = max(result, cnt);

                 }

        }

        cout << K - result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~