[BOJ_C++] 2628번 : 종이자르기

# 문제

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

int search(int* x, int size) {
    int max = -999, i = 0, j = 0;

    while (j < size) {
        j = i + 1;
        while (x[j] == 0) j++;
        if (max < j - i) max = j - i;
        i = j;
    }
    if (i != j) {
        if (max < j - i) max = j - i;
    }
    return max;
}

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

    int width, height; cin >> width >> height;
    int* w = new int[width+1]; memset(w, 0, sizeof(int)*width);
    int* h = new int[height+1]; memset(h, 0, sizeof(int)*height);
    w[width] = h[height] = 1;
    int n, type, m; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> type >> m;
        if (type == 0) h[m] = 1;
        else w[m] = 1;
    }

    printf("%d", search(w, width)*search(h, height));

    return 0;
}

• 먼저 너비와 높이를 입력받은 뒤, 입력받은 크기+1 만큼 배열을 각각 만든다. (자를 부분을 표시하기 위함)
• 가로로 자를지 세로로 자를지 type을 보고 판단하고 만약 세로로 자른다면 너비가 줄어드는 것이므로 w 배열의 m번째에 표시하고 가로로 자른다면 높이인 h 배열의 m번째에 표시한다.
• search 함수는 1 사이의 최대값을 찾아주는 함수이다.
• search 함수를 통해 각 최대 길이를 구하고 둘을 곱하면 구할 수 있는 최대 넓이가 된다.

#결과