백준 2628번 종이자르기 C++

문제 링크 : https://www.acmicpc.net/problem/2628

2628번: 종이자르기

 

문제 풀이

 이 문제는 모눈종이의 가로, 세로의 길이와 모눈종이 상의 자르는 선을 주어줬을 때, 나눠진 부분 중 가장 넓이가 큰 부분을 구하는 문제이다.

 

 최대 넓이를 구하려면 단순하게 가장 긴 가로 변과 가장 긴 세로 변의 길이를 구하면 된다. 구하는 방법은 먼저 column, row배열에 자르는 선인지에 대한 정보를 담고 각각의 배열에서 반복문을 1번씩만 돌아 최소길이를 구할 수 있다.

 

코드

#include <iostream>
using namespace std;

bool column[101],row[101];
int main()
{
    int W,H,N,mx_wi=0,mx_he=0,R=0,s,n;

    cin>>W>>H;
    cin>>N;
   
    column[W] = true;
    row[H] = true;
   
    while(N--)
    {
        cin>>s>>n;
        if(s==1)
        {
            column[n] = true;
        }
        else
        {
            row[n] = true;
        }
    }
   
    for(int i=1; i<=W; i++)
    {
       
            if(!column[i])
            {
                continue;
            }
           
            if(mx_wi<i-R)
            {
                mx_wi = i-R;
                R = i;
            }
            else
            {
                R=i;
            }
       
    }
   
    R=0;
    for(int i=1; i<=H; i++)
    {
       
            if(!row[i])
            {
                continue;
            }
           
            if(mx_he<i-R)
            {
                mx_he = i-R;
                R = i;
            }
            else
            {
                R=i;
            }
       
    }
   
    cout<<mx_he*mx_wi;
}