백준, BOJ, 2492번, 보석C++ [CPP] ★★★★

음.. 나올법한 문제지만.. 바로 생각나지 않았다.

이건 두고두고 볼만하긴 한 문제라고 생각한다.

어려웠다.

 

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

 

---

 

다음에 한 번 더 풀어야 겠다.

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int N,M,T,K;

int main(){
    cin >> N >> M >> T >> K;
    
    
    vector<pair<int,int>> jewel;
    
    for(int i = 0; i<T; i++){
        int x,y;
        cin >> x >> y;
        jewel.push_back({x,y});
    }
    
    int ansX,ansY;
    int ans = 0;
    
    //최적 사각형을 만드는 방법은 테두리에 보석이 포함될 때다.
    //즉, 사각형을 만들었을 때 보석이 변 위에 존재해야 한다.
    //(x1,y1)  (x2,y2) 라는 보석이 있을 때,
    //둘다 포함해야 하므로 사각형의 꼭지점은  c-l2 <= x1 <= c <= x2 <= c+l1
    //c는 저렇게 위치해야한다. 그리고 l1 + l2 는 k가 된다.
    //즉, 보석 2개를 골라서 저렇게 범위를 다 체크해보면 된다 100 * 99의 가지수가 나오겠다.
    
    //더 간단히 말하면 보석 한개의 x좌표와 다른 보석 한개의 y좌표를 왼쪽 위를 기준으로하여 정사각형을 그린다.
    
    //이 문제는 감이 안잡히면 못푸는 문제로.. 난 바로 못풀었다.
    
    
    for(int i = 0; i<T; i++){
        auto now = jewel[i];
        for(int j = 0; j<T; j++){
            //if(i == j)continue;   => 같은 보석이면 조사하지 않을 줄 알았는데... 아니더라.
            //같은 보석일 때 또한.. 조사를 해서 꼭짓점을 결정시켜야 하더라.. 어려운 문제다.
            int dx,dy;
            auto comp = jewel[j];
            if(now.first + K > N) dx = N - K;
            else dx = now.first;
            
            if(comp.second + K > M) dy = M -K;
            else dy = comp.second;
            
            //dx,dy를 좌측 위 꼭짓점으로하는 정사각형 안의 보석 개수
            int temp = 0;
            for(auto jew : jewel){
                if(dx <= jew.first && jew.first <= dx + K && dy <= jew.second && jew.second <= dy + K){
                    temp++;
                }
            }
            if(temp > ans){
                ansX = dx;
                ansY = dy + K;  //?
                ans = temp;
            }   
        }
    }
    
    
    cout << ansX << " " << ansY << '\n';
    cout << ans << '\n';
    
    
    
    return 0;
}