글 읽기 - 시간초과가 납니다.. 아무리 봐도 모르겠습니다.

johoon4687sub 2년 전 0

여러 테스트케이스들은 다 통과를 했는데 제출하면 시간초과가 납니다. 무한루프가 걸리는건가 싶어서 찾아보았지만 찾지 못 했습니다.. 도와주세요 ㅠㅡㅠ

#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;

// s 에서 시작해서 어디까지 갔나?
int dfs(vector<int>& student, vector<int>& visit, vector<int>& curList, 
	const int s, int cur, int cnt) {

	// 이미 방문이 된 곳?
	if (visit[cur]) {
		// 	   이미 팀이 있는 경우 -> 셀프팀도 포함
		if (curList[cur]) { // 	   현재 탐색중인 학생인 경우
			return cnt - curList[cur];
		}
		else {
			return 0;
		}
	}
	else {// 아직 방문이 되지 않은 곳?
		visit[cur] = true;
		curList[cur] = cnt;
		return dfs(student, visit, curList, s, student[cur], cnt + 1);
		//     계속해서 탐색 
	}
}

int solve(vector<int>& student, const int& n) {
	vector<int> visit(n + 1, false); // 이미 팀의 여부를 아는 사람들

	int ret = n;

	for (int i = 1; i <= n; i++) { // i'th student check
		if (visit[i]) continue;
		vector<int> curList(n + 1, 0);
		ret -= dfs(student, visit, curList, i, i, 1);
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int tc, n;

	cin >> tc;

	while (tc--) {
		cin >> n;

		vector<int> student(n + 1);

		for (int i = 1; i <= n; i++) {
			cin >> student[i];
		}

		ans.push_back(solve(student, n));
	}

	for (int e : ans) cout << e << '\n';
}

johoon4687sub 2년 전 2

37번째 줄에서 방문하지 않은 노드에 도착했을 때 마다 n 크기의 배열을 계속해서 선언을 해 준 것이 문제였습니다.

이 경우 10만명 학생들이 모두 혼자 팀을 하려고 한 테스트 케이스에는 O(N^2) 의 시간복잡도가 걸리는 것을 간과하고 있었습니다..

N이 10만일 때 N^2 = 10'000'000'000 ..... 입니다... ^^

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

문제

문제

출처

ICPC

시간초과가 납니다.. 아무리 봐도 모르겠습니다.

johoon4687sub 2년 전 0

johoon4687sub 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말