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

https://boj.ma/14658/t 

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

L*L 사이즈의 트램펄린을 설치해서 최대한 많은 별똥별을 튕겨내는게 목적인 문제입니다.

 

완전탐색부터 접근해 봅니다.

 

첫번째로 모든 별의 조합을 생각해봅니다.

별 K개중 1개만 선택했을 때 L*L 사이즈로 막을 수 있는지,

2개 선택했을때 막을 수 있는지, ... K개 선택했을때 막을 수 있는지.

모든 별의 조합을 보며 막을 수 있는 최대 갯수를 구하면 됩니다

경우의 수가 공집합을 제외한 부분집합의 합이 되어 이 경우의 수는 2^K - 1가지 경우만 보면 됩니다.

하지만 K가 최대 100이므로 O(2^100)으로 제한시간 내에 계산할 수 없습니다.

 

두번째로 모든 좌표에 대해 생각을 해봅니다.

별똥별이 떨어질 수 있는 범위가 N*M 사이즈 이니

1, 1부터 N,M까지 모든 좌표를 왼쪽 아래 좌표로 하는 L*L사이즈의 트램펄린을 놔보며 튕겨나가는 별똥별의 갯수를 세어주면 답을 찾을 수 있을것 같습니다.

하지만 N, M <= 5 *10^5 이기때문에 시간초과입니다.

 

두가지 완탐 접근을 생각해봤고, 둘 다 시간초과인 것을 확인했습니다.

이제 최적화에 대해 생각해봅니다.

 

1. 모든 별의 조합을 본다

얘는 아마도 백트래킹 형태로 진행하게 될텐데. 조합을 고르며

답이 될 수 없는 점 조합을 가지치기로 거르면 될 것 같습니다.

고른 별들이 이미 L*L 범위 내에 함께 들어올 수 없는 경우가 되겠습니다.

 

2. 모든 좌표를 본다

얘에서 최적화는 답이 될 수 없는 좌표를 거른다로 자연스럽게 생각의 흐름이 가야합니다.

그렇다면 답이 될 수 없는 좌표는 뭐가 될까요?

관찰을 해봅시다.

N, M 이 50만, 트램펄린의 길이가 5라고 생각해봅니다.

그리고 주어진 점들이

(1, 1), (2, 2), (3, 3), (4, 4)라고 생각해봅시다

두번째 완탐 접근에서는 1,1 부터 N,M까지 N*M가지 점들에 대해 확인하는데,

위와 같이 점이 주어졌을때 5, 5같은 점들에 대해 볼 필요가 있을까요? 당연히 필요없습니다.

우리는 점이 있는 x좌표, 점이 있는 y좌표에 대해서만 트램펄린을 놔보면 됩니다.

별똥별의 갯수가 최대 100개니까

O(K^2) 가지의 점들에 대해 트램펄린을 놔보며 K개의 별을 확인하면 되므로

O(K^3) 번만 연산하면 됩니다.

K <= 100이므로 시간내에 충분히 가능합니다.

 

코드(c++)

#include <bits/stdc++.h>
#define endl "\n"
#define NM 201010
#define MAX 1010100
#define BIAS 100000
#define MOD 1000000007
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;


int main() {
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m, l, k;
    cin >> n >> m >> l >> k;
    vector<pii> dot(k);
    vector<int> x(k), y(k);
    for (int i = 0 ; i < k; i++){
        cin >> dot[i].X >> dot[i].Y;
        x[i] = dot[i].X;
        y[i] = dot[i].Y;
    }
    int ans = k;
    for (int i = 0; i < k; i++){
        for (int j = 0 ; j < k; j++){
            int cx = x[i];
            int cy = y[j];
            int lx = cx + l;
            int ly = cy + l;
            int cnt = k;
            for (auto d : dot){
                if (cx <= d.X && d.X <= lx && cy <= d.Y && d.Y <= ly) cnt--;
            }
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
    return 0;
}

 

 

 

 

 

아래는 정확히 똑같은 아이디어를 이용하는 문제들입니다.

 

 

https://boj.ma/14718/t 

14718번: 용감한 용사 진수

https://boj.ma/1090/t 

1090번: 체커