문제 링크 : https://www.acmicpc.net/problem/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;
}
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 1654번 랜선 자르기 C++ 이분탐색 (0) | 2024.01.27 |
---|---|
백준 1713번 후보 추천하기 C++ (1) | 2024.01.06 |
백준 2302번 극장 좌석 C++ (1) | 2023.12.17 |
백준 17615번 볼 모으기 C++ (1) | 2023.12.17 |
백준 10799번 쇠막대기 C++ (1) | 2023.12.16 |