글 읽기 - 1931 시간초과

hjm7712 4년 전 0

채점 6프로에서 자꾸 막히는데

sorting 부분에서 막히는건지 아니면 비교하는 과정에서 막히는 건지 잘 모르겠습니다

29번째 줄에서 있는 코드는 각 회의까지 했던 회의들의 최대값들입니다.

i번째 회의 시작 시간보다 앞선 회의들의 최댓값을에서 1을 더해 i번째를 완성해 나가는 방식으로 했는데 어떤 부분을 고쳐야 시간 초과를 해결할 수 있을지 모르겠습니다...

질문에 나와있던 여러 예제나 반례를 했을 때 틀린 답이 나오지는 않았습니다.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std; 

typedef struct{
	int start;
	int end;
	int conf;
}data;

bool operator<(data a,data b){
	return a.start<b.start;
}

int main() {
	int num,max_n=1;
	scanf("%d",&num);
	list<data> l;
	for(int i=0;i<num;i++){
		int start,end;
		scanf("%d %d",&start,&end);
		l.push_back({start,end,1});
	}
	
	l.sort();
	
	list<data>:: iterator ii;
	for(ii=l.begin();ii!=l.end();ii++){
		list<data>:: iterator jj;
		for(jj=l.begin();jj!=ii;jj++){
			if((*ii).start>=(*jj).end&&(*ii).conf<(*jj).conf+1){
				(*ii).conf=(*jj).conf+1;
				if(max_n<(*ii).conf)	max_n=(*ii).conf;
			}
		}
	}
	
	printf("%d",max_n);
	
}

heiler 4년 전 0

위의 로직으로 답은 나오겠지만 line 29-37의 시간복잡도는 O(n^2)입니다.

n이 10만이기 때문에 n^2으로는 시간제한 내에 해결할 수 없습니다. O(nlogn)에 해결할 수 있는 방법을 생각해보셔야 합니다.

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

문제

문제

출처

ICPC

1931 시간초과

hjm7712 4년 전 0

heiler 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말