https://www.acmicpc.net/problem/14658
2D 평면에서 고정 크기 사각형으로 최대 점 커버하기 문제다.
- 모든 좌표를 탐색하면 N, M <= 500,000 이므로 O(n^2)시 시간 초과가 난다.
- 어떤 좌표만 봐야할까?
- 특이한 점만을 찾아 조져(?)야 된다고 판단.
별똥별이 트램펄린의 왼쪽 변 또는 아래 변에 딱 걸쳐 있는 경우만 조사해보자.
어떤 최적 위치가 있다고 하자:
┌─────────┐
│ ★ ★ │
│ │
│ ★ │
└─────────┘
이 트램펄린을 왼쪽으로 밀면?
→ 별이 빠져나가기 전까지는 커버 수가 그대로
그러다 별이 왼쪽 경계에 닿는 순간:
┌─────────┐
★ ★ │ ← 이 위치도 똑같이 최적이다.
│ │
│ ★ │
└─────────┘
for(int i=0; i<K; i++){ // 별똥별 i의 y좌표를 트램펄린 시작 y로
for(int j=0; j<K; j++) { // 별똥별 j의 x좌표를 트램펄린 시작 x로
res = max(res, go(star[i].first, star[j].second));
}
}
모든 (별똥별 y, 별똥별 x) 조합 -> K^2 개만 검사하면 된다.
전체 코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
int N, M, L, K, res;
// 별똥별 좌표
vector<pair<int, int>> star;
int go(int y, int x) {
int cnt = 0;
for(auto &cur: star) {
if ((y <= cur.first && cur.first <= y + L)
&& (x <= cur.second && cur.second <= x + L)) {
cnt++;
}
}
// cout << cnt << "\n";
return cnt;
}
int main() {
cin >> N >> M >> L >> K;
for(int i=0;i<K;i++){
int y, x;
cin >> y >> x;
star.push_back(make_pair(y, x));
}
for(int i=0;i<K;i++){
for(int j=0;j<K;j++) {
res = max(res, go(star[i].first, star[j].second));
}
}
cout << K - res << "\n";
return 0;
}
반응형
'PS' 카테고리의 다른 글
| [프로그래머스 Lv.2] 완전범죄 (0) | 2025.12.08 |
|---|---|
| [BOJ 2179] 비슷한 단어 (0) | 2025.12.08 |
| 코테 공부 07.07 (0) | 2025.07.07 |
| 코테 공부 6.28 (0) | 2025.06.28 |
| 코테 공부 No.1 (1) | 2025.06.27 |