글 읽기 - 시간초과를 어떻게 잡아야 하는걸까요?

nothappa 5년 전 0

50%대에서 오래 걸리다가 54%에서 시간초과로 터집니다.

현재 canp[] 배열에 1번 조건 (1번 항목에서 1위를 한 사람의 2번 항목의 순위 보다 낮은 모든 사람들을 제거)값을 넣어서 비교할 배열 크기를 줄였고,

3번에서 남들보다 부족한게 나오는 사람을 컷하고 있는 코드입니다.

문제가 3번 비교문인 57~64번줄에서 발생중인거 같은데,

머리를 굴려봐도 시간복잡도를 O(N)으로 떨어뜨릴 방법은 안나오는거 같고,

잘 해봐야 O(nlogn)이나, 반복수를 최소화 시킨 O(n^2)이 한계인거 같은데..

개선 방법 힌트를 얻고 싶습니다.

#include <iostream>
using namespace std;
int people[100001];		//인원
int canp[100001]; // 가능성 있는 인원
bool pass[100001]={0};
void answer(int number);
int main() {
	// your code goes here
	int loop;
	int numb;
	cin >> loop;
	
	for(int i = 0 ; i<loop;i++){
	scanf("%d",&numb);
	answer(numb);
	}
	
	return 0;
}
void answer(int number){
	int result = 0;

	int a,b;
	bool index1=false;
	bool index2=false;
	int candi=1;
	for (int i = 1 ; i < number+1 ;i ++){
	scanf("%d%d",&a,&b);
	people[a]=b;	
	}
	//for(int i = 1 ; i<number+1;i++)
	//cout<<i<<","<<people[i]<<endl;
	//std::sort(people,&people[N-1]+1);
	//1.첫번째 항목에 대해 1빼고 전부 false
	//2.두번째 항목에서 1번 항목 1등의 점수보다 높은 애들만 true
	//3.걸러진 애들 중 두개의 순위가 다른 애들보다 낮은애들 cut
	
	//1. -> 자동
	pass[1]=true;
	//canp[1][0]=1;
	canp[1]=people[1];
	//2.
	for (int i = 2 ; i<number+1;i++){
		if(people[1]>people[i]){
		pass[i]=true;
		candi++;
		
		canp[candi]=people[i];
		}
	}
	
	//3.

	
	result=candi;

		for (int i = 1 ; i <candi+1 ; i ++){
		for (int j=1;j<candi+1;j++){
			if(i>j&&canp[i]>canp[j]){
			result--;
			break;
			        }
		        }
		  }	
                   
	printf("%d\n",result);
}

nothappa 5년 전 0

판단 알고리즘을 아예 새로 짜서 해결했습니다.

하고나니 엄청 허무하네요.

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

문제

문제

출처

ICPC

시간초과를 어떻게 잡아야 하는걸까요?

nothappa 5년 전 0

nothappa 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말