[백준] 2628번 : 종이자르기

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

해결책:

– 주어진 가로점선과 세로점선을 따라 종이를 자를 때 가장 큰 정사각형을 찾아보세요.

– 누적합에서 구간의 길이를 구하는 방법과 동일합니다.

– 위도가 2 3 5라고 가정하고,

현재 i는 2이고 0~2의 크기는 i의 값, 즉 2입니다.

현재 i는 3이고 2에서 3까지의 크기는 i – (i – 1), 3 – 2 = 1의 값입니다.

현재 i는 5이고 3에서 5까지의 크기는 i – (i – 1), 5 – 3 = 2의 값입니다.

-> 현재 값은 0보다 크면 이전 값을 빼야만 구할 수 있습니다.

– 길이는 같은 방법으로 구할 수 있으며, 구한 가로와 세로를 곱하여 정사각형의 크기를 구할 수 있습니다.

– 이전 값을 기준으로 계산되므로 정렬하는 것을 잊지 마십시오.

암호:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int width, height, n, num, get_width, get_height;
    vector<int> arr_width; //가로로 자르는 점선 번호 저장
    vector<int> arr_height; //세로로 자르는 점선 번호 저장
    bool is_it_height;

    cin >> width >> height >> n;
    for(int i=0; i<n; i++){
        cin >> is_it_height >> num;
        if(is_it_height){ //1이라면 세로
            arr_height.push_back(num);
        }else{
            arr_width.push_back(num);
        }
    }

    arr_width.push_back(height); //세로 길이 저장
    arr_height.push_back(width); 
    sort(arr_height.begin(), arr_height.end()); //오름차순으로 정렬
    sort(arr_width.begin(), arr_width.end());

    num = 0;
    for(int i=0; i<arr_width.size(); i++){ //각 네모의 크기를 구하는 과정
        for(int j=0; j<arr_height.size(); j++){ 
            get_width = arr_width(i); //현재 위치의 가로 길이 대입
            get_height = arr_height(j);
            if(i > 0){ //i가 0보다 크다면
                get_width -= arr_width(i-1); //현재 값-이전 값을 함으로 현재 위치의 박스의 가로 길이 도출 
            } if(j > 0){
                get_height -= arr_height(j-1); //세로 길이 도출
            }
            num = max((get_width * get_height), num); //위에서 구한 박스 크기와 num 비교해서 더 큰 값 num에 대입 
        }
    }
    cout << num << '\n';
}