글 읽기 - 시간초과가 나는데 도저히 모르겠습니다. 부디 가르침을 주세요 ㅠㅠ

meenook1109 3년 전 0

나무 재테크를 C로 짯는데 왜 시간초과가 나는지 모르겠습니다. 먼저 살아있는 나무와 죽은 나무를 봄 단계에서 구별해주고 죽은 나무만 여름에 처리하고 가을에는 살아있는 나무만 처리합니다. 그리고 새로 태어난 나무는 번식하지 않기 때문에 무시합니다. 아무리 생각해도 K*cnt정도 의 복잡도 같은데 qsort가 bottleneck일까요? 아니면 더 줄여야 하는 것일까요?도와주십쇼 ㅠㅠ

#include<stdio.h>

typedef struct TREE{
	int r,c,age,dead;
}TREE;

TREE tree[110000],livetree[110000],deadtree[110000];
int livecnt,deadcnt;
int N,K,M,cnt;
int add[12][12];
int map[12][12];
print(){
	int i;
	for(i=0;i<cnt;i++){
		printf("tree[%d] r:%d c:%d age:%d dead:%d\n",i,tree[i].r,tree[i].c,tree[i].age,tree[i].dead);
	}
}
int comp(const void* a, const void* b){
	TREE x=*(TREE*)a;
	TREE y=*(TREE*)b;
	if(x.age>y.age) return 1;
	else if(x.age==y.age) return 0;
	else return -1;
}
void spring(){
	qsort(tree,cnt,sizeof(TREE),comp);
	int i;
	livecnt=0,deadcnt=0;
	for(i=0;i<cnt;i++){
		int nr=tree[i].r;
		int nc=tree[i].c;
		int age=tree[i].age;
		if(age<=map[nr][nc]){
			map[nr][nc]-=age;
			tree[i].age++;
			livetree[livecnt]=tree[i];//살아있는 나무 저장 
			livecnt++;
		}else{
			deadtree[deadcnt]=tree[i];//죽은나무 저장 
			deadcnt++;
		}
	}
	
}
void summer(){
	int i;
	for(i=0;i<deadcnt;i++){
		int nr=deadtree[i].r;
		int nc=deadtree[i].c;
		int age=deadtree[i].age;
		map[nr][nc]+=age/2;
	}
}
void fall(){
	int dr[]={0,1,0,-1,1,-1,1,-1};
	int dc[]={1,0,-1,0,1,1,-1,-1};
	int i,j,count;
	count=livecnt;
	for(i=0;i<count;i++){//살아있는 나무만 번식새로태어난 나무는 무조건 살아있고 번식하지 않으므로 무시. 
		tree[i]=livetree[i];	//살아있는 나무 tree로 이동	
		if(livetree[i].age%5==0){
			for(j=0;j<8;j++){
				int nr=livetree[i].r+dr[j];
				int nc=livetree[i].c+dc[j];
				if(nr<1||nr>N||nc<1||nc>N) continue;
				tree[livecnt].r=nr;
				tree[livecnt].c=nc;
				tree[livecnt].age=1;
				livecnt++;
			}
		}
	}
	cnt=livecnt;
	//printf("%d\n",cnt);
}
void winter(){
	int i,j;
	for(i=1;i<=N;i++){
		for(j=1;j<=N;j++){
			map[i][j]+=add[i][j];
		}
	}
}
int main(){
	
	scanf("%d %d %d",&N,&M,&K);
	int i,j;
	for(i=1;i<=N;i++){
		for(j=1;j<=N;j++){
			scanf("%d",&add[i][j]);
			map[i][j]=5;
		}
	}
	for(i=0;i<M;i++){
		scanf("%d %d %d",&tree[i].r,&tree[i].c,&tree[i].age);
		cnt++;
	}
//	init();

	for(i=0;i<K;i++){
		spring();
		summer();
		fall();
		winter();
	}
	
	printf("%d\n",livecnt);
}
/*
10 10 1000
100 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
6 6 1
7 7 1
8 8 1
9 9 1
10 10 1

10 100 1000
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
1 1 4
1 2 4
1 3 4
1 4 4
1 5 4
1 6 4
1 7 4
1 8 4
1 9 4
1 10 4
2 1 4
2 2 4
2 3 4
2 4 4
2 5 4
2 6 4
2 7 4
2 8 4
2 9 4
2 10 4
3 1 4
3 2 4
3 3 4
3 4 4
3 5 4
3 6 4
3 7 4
3 8 4
3 9 4
3 10 4
4 1 4
4 2 4
4 3 4
4 4 4
4 5 4
4 6 4
4 7 4
4 8 4
4 9 4
4 10 4
5 1 4
5 2 4
5 3 4
5 4 4
5 5 4
5 6 4
5 7 4
5 8 4
5 9 4
5 10 4
6 1 4
6 2 4
6 3 4
6 4 4
6 5 4
6 6 4
6 7 4
6 8 4
6 9 4
6 10 4
7 1 4
7 2 4
7 3 4
7 4 4
7 5 4
7 6 4
7 7 4
7 8 4
7 9 4
7 10 4
8 1 4
8 2 4
8 3 4
8 4 4
8 5 4
8 6 4
8 7 4
8 8 4
8 9 4
8 10 4
9 1 4
9 2 4
9 3 4
9 4 4
9 5 4
9 6 4
9 7 4
9 8 4
9 9 4
9 10 4
10 1 4
10 2 4
10 3 4
10 4 4
10 5 4
10 6 4
10 7 4
10 8 4
10 9 4
10 10 4


*/

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

문제

문제

출처

ICPC

시간초과가 나는데 도저히 모르겠습니다. 부디 가르침을 주세요 ㅠㅠ

meenook1109 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말