사용한 알고리즘
알고리즘 설명
- 두 개의 배열을 생성하여 잘려진 지점을 저장한다.
- 두 배열은 x축의 잘린지점과 y축의 잘린 지점을 저장한다.
- 두 잘린지점을 각각 모두 저장한뒤에 정렬한다.
- 이를 이용하면 잘린 뒤 만들어진 모든 사각형을 표현할 수 있다.
- 공식은 아래와 같다.
사각형 넓이 = (xaxis(i+1)-xaxix(i))*(yaxis(j+1)-yaxis(j))- 위 공식으로 모든 i(x축 잘린 개수)와 모든 j(y축 잘린 개수)를 이용하여 사각형 크기를 측정한다.
- 코드를 쉽게 하기 위해 xaxis(0)와 yaxis(0)를 처음 지점인 0으로 설정하고, xaxis(xend+1)와 yaxis(yend+1)는 C와 R(각 사각형 바운드)를 저장한다.
- 모든 사각형 중에 가장 큰 사각형을 출력한다.
풀이
// baekjoon 2628 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=101;
int R, C, K, xaxis[MAX_N], yaxis[MAX_N];
int ret, xpos, ypos, cmd, value;
int main() {
scanf("%d%d", &C, &R);
scanf("%d", &K);
// 0번째 인덱스는 초기 0으로 설정
xaxis[xpos++]=0;
yaxis[ypos++]=0;
// 잘려지는 지점 저장하기
for (int i=0; i<K; i++) {
scanf("%d %d", &cmd, &value);
if (cmd) xaxis[xpos++] = value;
else yaxis[ypos++] = value;
}
// 마지막 값에는 종이의 마지막 지점인 가로와 세로 값 저장
xaxis[xpos++]=C;
yaxis[ypos++]=R;
// 이를 정렬함
sort(xaxis, xaxis+xpos);
sort(yaxis, yaxis+ypos);
// 모든 사각형에 접근하여 가장 큰 사각형을 ret에 저장
for (int i=0; i<xpos-1; i++)
for (int j=0; j<ypos-1; j++)
ret = max(ret, (xaxis[i+1]-xaxis[i])*(yaxis[j+1]-yaxis[j]));
// 결과 출력
printf("%d\n", ret);
return 0;
}
