종이자르기 (feat. 백준, 2628번)

종이자르기
https://www.acmicpc.net/problem/2628

2628번: 종이자르기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int C, R, N;
    vector<int> arr_c, arr_r;
    cin >> C >> R >> N;
    arr_c.push_back(0), arr_c.push_back(C);
    arr_r.push_back(0), arr_r.push_back(R);
    for(register int n = 0, x, y; n < N; ++n){
        cin >> x >> y;
        if(x == 1)
            arr_c.push_back(y);
        else
            arr_r.push_back(y);
    }
    sort(arr_r.begin(), arr_r.end());
    sort(arr_c.begin(), arr_c.end());
    vector<int> ans_c, ans_r;
    for(auto idx = 0; idx < arr_c.size() - 1; ++idx)
        ans_c.push_back(arr_c[idx + 1] - arr_c[idx]);
    for(auto idx = 0; idx < arr_r.size() - 1; ++idx)
        ans_r.push_back(arr_r[idx + 1] - arr_r[idx]);
    cout << *max_element(ans_c.begin(), ans_c.end()) * *max_element(ans_r.begin(), ans_r.end());
	return 0;
}
// *&)*@*

 

반응형

1. 자르는 행과 열의 구간들을 각각 저장합니다.
2. 행과 열을 정렬 후 앞과 뒤의 차이를 각각 저장합니다.
3. 2번의 행과 열의 차이값 중 가장 큰 값 끼리 곱한 결과가 정답입니다.