글 읽기 - 1766번 질문드립니다~

algospot 8년 전 0

문제점이 2가지 있습니다.

1번) 메모리를 잡으려니 너무 커서 구조체를 써볼까 하니 뭐 매 한가지인데, vector 쓰는 법 외엔 없는건가요?

vector를 안쓰고 풀고 싶습니다. 모든 문제를 #include <stdio.h> 로만 문제를 풀고있고, 모든 걸 구현하면서 하는 걸 목적으로 두고 있어서요..

2번) 설사 메모리를 잡았다 하더라도, while(rest--) 내에서 sum[i]==0 이 되는 걸 매번 N번 검사하는데 그걸 줄일수있는 방법이 있나요?

sum을 매번 정렬해서 이진검색하자니, 정렬비용*이진검색이나, 그냥 N번이나;;

#include <stdio.h>
int N,M;
int dap[32011];
typedef struct G {
	int cnt;
	int conn[1001];
};
G g[1011];
int sum[32011];
int TS() {
	int i,j,cnt=-1;
	int rest=N;
	while(rest--) {
		for(i=1;i<=N;i++) {
			if(sum[i]==0) break;
		}
		if(i==N+1) return 0;
		sum[i]=-1;
		dap[++cnt]=i;
		for(j=0;j<g[i].cnt;j++) sum[g[i].conn[j]]--;
	}
	return 1;
}
int main(void) {
	int i,j,a,b;
	scanf("%d%d",&N,&M);
	for(i=0;i<M;i++) {
		scanf("%d%d",&a,&b);
		g[a].conn[g[a].cnt++]=b; //a->b
		sum[b]++;
	}
	if(TS()) for(i=0;i<N;i++) printf("%d ",dap[i]);
	else printf("-1");
	return 0;
}

yukariko 8년 전 0

저도 stl에 의존하지않고 이 문제를 해결하였는데, queue와 heap을 이용해 해결하였습니다.

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

문제

문제

출처

ICPC

1766번 질문드립니다~

algospot 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말