글 읽기 - 시간초과 지적좀 해주세요ㅠㅠ

eclair22 6년 전 0

시간초과가 나오는데....

지적 부탁드립니다.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int t,i,j,k,m,n,now;
	int end = 0;
	int po = 0;
	int pop = 0;
	int *result;
	int *stu;
	int *nstu;
	int *st;
	
	scanf("%d", &t);
	result = (int*)malloc(sizeof(int)*(t+1));

	for (i = 0; i < t; i++) {
		result[i] = 0;
		scanf("%d",&n);
		stu = (int*)malloc(sizeof(int)*(n+1));
		
		for(j=1;j<(n+1);j++)
			scanf("%d",&stu[j]);
		nstu = (int*)malloc(sizeof(int)*(n+1));

		for (j = 1; j < (n+1); j++) {
			st = (int*)malloc(sizeof(int)*(n+1));
			now = j;
			while (end == 0) {
				st[pop] = now;
				pop += 1;
				
				for (k = 0; k < pop; k++) {
					if (st[k] == stu[now]) {
						end = 1;
						for (m = 0; m < k; m++) {
							nstu[po] = st[m];
							po += 1;
						}
						break;
					}
				}
				if (end != 1)
					now = stu[now];
			}
			free(st);
			pop = 0;
			end = 0;
		}
		for (j = 0; j < po; j++) {
			for (k = j+1; k < po; k++) {
				if (nstu[j] == nstu[k]) nstu[k] = 0;
			}
		}

		for (j = 0; j < po; j++) {
			if (nstu[j] != 0) result[i] += 1;
		}
		free(nstu);
		po = 0;
		free(stu);
	}
	for (i = 0; i < t; i++)
		printf("%d\n",result[i]);

	free(result);
	return 0;
}

chogahui05 6년 전 0

어떻게 푸셨는지 설명해 주실 수 있으신가요?

eclair22 6년 전 0

처음에 입력받아야할 것 모두 입력받고

1번부터 시작해서 확인합니다.

1번의 값을 보기 전 1이란 숫자를 st(스택)이라는 공간에 넣고 이 스택과 1번이 가리키는 곳의 값을 비교합니다.

같은것이 있다면 (사이클이 반복된다면)

스택내에서 pop 이전에 해당하는 숫자, 즉 사이클이 반복되지 않는 숫자를 다시 다른 공간에 저장하고 1번의 사이클을 종료합니다.

말을 조리있게 잘 못해서... 그림으로 설명해드리고 싶은데 이거 처음이라 잘 모르겠네요ㅠㅠ

chogahui05 6년 전 0

사이클이 있다면 탐색을 하다가 빠져 나오는군요.

그러면

1 - 2 - 3 - 4 - 5 - ... - 100000 - 1

이라는 사이클이 있을 때 어떤 식으로 동작하나요?

1을 방문해서 사이클을 탐색했을 때, 2를 방문하지 않는다는 보장이 있나요?

만약에 1을 탐색했는데 또 2를 탐색한다면.. 그것 때문에 시간초과가 날지도 모르지요.

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

문제

문제

출처

ICPC

시간초과 지적좀 해주세요ㅠㅠ

eclair22 6년 전 0

chogahui05 6년 전 0

eclair22 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말