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

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

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';
}