2628 종이자르기 (백준)

 

뭔 생각이 부족해서 못 풀었나

가로(y) 세로(x) 좌표만 따로 벡터로 받아서 먼저 정렬한 뒤, 최대 가로 세로 길이를 구한 후 그 두개를 곱해서 답을 냈어야 한다.

가로 세로 좌표를 따로 받을 생각을 하지 못했고 같이 받아버리고 해결하려는 잘못된 접근의 문제가 컸다.

 

뭘 실수해서 틀렸나

생각 자체가 안났고 실수라고 할것 없이 아이디어가 안떠오른 문제이다.

 

그래서 뭘 기억하면 되나

넓이 구하는 문제가 나왔고, 좌표가 나올땐 그걸 정렬한후 인접한 두 좌표끼리 빼서 최대 최소 가로세로 길이를 구할수가 있다. 그걸로 둘레나 넓이를 활용하면 된다. 

 

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

int main(){

    cin.tie(0) -> sync_with_stdio(0);

    int x, y, n;
    cin >> x >> y >> n;

    vector<int> hori  = {0, y};
    vector<int> verti = {0, x};

    for (int i = 0; i < n; i++){

        int direction;
        int dot;
        cin >> direction >> dot;

        if (direction == 0){
            hori.push_back(dot);
        }else{
            verti.push_back(dot);
        }
    }
    
    sort(hori.begin(), hori.end());
    sort(verti.begin(), verti.end());

    int maxh = 0; int maxw = 0;

    for (int i = 1; i < hori.size(); i++){
        maxh = max(maxh, hori[i] - hori[i - 1]);
    }
    for (int i = 1; i < verti.size(); i++){
        maxw = max(maxw, verti[i] - verti[i - 1]);
    }    

    int ans = maxh * maxw;

    cout << ans; 

}