글 읽기 - 3321번 가장 큰 직사각형 문제 질문입니다.

kks227 9년 전 0

예제는 잘 나오는데, 4%에서 틀렸다고 하네요.

알고리즘은 이렇습니다.

매 행에 대해서, M칸짜리 배열을 만드는데 이는 i번째 행의 각 원소에 대해

원소가 0이면 0, 원소가 1이면 자신을 포함하여 위에 있는 연속된 1의 개수입니다.

그리고 이를 히스토그램처럼 생각하여 소팅한 후 왼쪽부터 가능한 모든 직사각형 넓이를 구하며

가장 큰 것을 구하는데요,

알고리즘이 틀린 것인가요? 소팅을 하면 안 되나요?

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char map[15000][1501];

int main(){

	int N, M, result = 0;
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; i++)
		scanf("%s", map[i]);

	char h[1500] = {0}, h2[1501];
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(map[i][j] == '1') h[j]++;
			else h[j] = 0;
		}
		memcpy(h2, h, M);
		sort(h2, h2+M);
		reverse(h2, h2+M);
		h2[M] = 0;
		for(int j=0; j<M; j++){
			if(h2[j] == 0) break;
			if(h2[j+1] == h2[j]) continue;
			result = max(result, (j+1)*h2[j]);
		}
	}
	printf("%d\n", result);

	return 0;
}

ainch96 7년 전 0

그 궁금한게 있는데.... 높이를 저장하는 배열에서 (h, h2 배열) 만약 높이 값이 너무 커지면 char으로 표시 할 수 있는 범위를 넘어가지 않을까요...?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3321번 가장 큰 직사각형 문제 질문입니다.

kks227 9년 전 0

ainch96 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말