글 읽기 - 3321번 문제 시간 초과 질문

nuclear852 5년 전 0

3321번 직사각형 최대 넓이 맨 처음에는

열 바뀌는줄 모르고 히스토그램의 넓이 구하는 것처럼 했다가 열 바뀌는 것을 깨닫고 코드를 고쳤는데요,,,

구하는 방법은 i번째 줄(0~N-1)에서 나올 수 있는 높이들을 구한다음에 (높이란 위에 연속적으로 있는 1의 갯수)

이를 소팅해서 넓이 후보를 구해준다음 계산하는 방식입니다.

9%에서 시간초과가 뜹니다.

O(nm + nm + n(m+mlgm)) = O(nmlgm)으로 짠거 같은데 시간 초과나서 질문 드립니다.

이전 질문에 보면 O(nm)으로 짜는게 정해이지만 O(nmlgm)도 통과된다고 해서.. 어느 부분이 시간초과하는 원인인지 잘 모르겠습니다... 정해 방법도 힌트를 주시면 감사하겠습니다 ㅠ

#include <stdio.h>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
short d[15000][1500];
bool map[15000][1500];
int N, M;
int MAX = 0;
int max(int a, int b){return a>b?a:b;}

int calculate(int x){
	int temp_MAX = 0;
	vector<int> v;
	for(int i=0; i<M; i++){
		v.push_back(d[x][i]);
	}
	sort(v.begin(), v.end());
	int idx = 1;
	for(int i=v.size()-1; i>=0; i--){
		temp_MAX = max(temp_MAX, v[i]*idx++);
	}
	return temp_MAX;
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	for(int i=0; i<M; i++){
		for(int j=N-1; j>=0; j--){
			if(j==N-1) d[j][i] = map[j][i];
			else if(map[j][i] == 0) d[j][i] = 0;
			else d[j][i] = d[j+1][i] + map[j][i];
		}
	}
	for(int i=0; i<N; i++){
		MAX = max(MAX, calculate(i));
	}
	printf("%d", MAX);
}

Green55 5년 전 1

O(NMlogM)이 맞지만 상수컷팅이 필요할 것 같습니다.

저는 cin으로 문자열로 입력받아 1412ms로 통과했는데, 입력 방식을 작성자님처럼 바꿔보니 바로 시간초과가 나네요.

O(NM)풀이는, 바로 윗 행에서 정렬해놓은 정보를 이용해서, 이번 행의 정보를 O(M)으로 정렬 하는 방법을 생각해 보세요.

nuclear852 5년 전 0

와 진짜 문자열로 입력받으니까 통과되긴 하네요

진짜 감사합니다 ㅋㅋ

O(M) 정렬방법도 고민해보겠습니다 감사합니다~

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

문제

문제

출처

ICPC

3321번 문제 시간 초과 질문

nuclear852 5년 전 0

Green55 5년 전 1

nuclear852 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말