글 읽기 - C++ 시간초과 ㅠㅠ

fdhyunseo 2년 전 0

제 컴퓨터에서는 엔터 누르자마자 바로 답이 나오는데, 왜 시간 초과가 뜰까요 ㅠㅠ

이 문제에서 시간복잡도 O(n³)는 무겁나요?

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> 
#include <cmath>
#include <math.h>
#include <iomanip>
#include <tuple>

using namespace std;
#define ll long long int

int kids[51][2501];
int kidsCount[51];

int find(int d, int l, int n) {

	int left = 0;
	int right = l;
	int m = (left + right) / 2;

	while (right - left >= 0) {
		if (kids[d][m] == n) {
			return 1;
		}
		else if (kids[d][m] <= n) {
			left = m + 1;
		}
		else {
			right = m - 1;
		}

		m = (left + right) / 2;
	}

	return 0;
}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;

		if (k == -1) {
			continue;
		}
		else {
			kids[k][kidsCount[k]] = i;
			kidsCount[k] += 1;
			for (int j = kidsCount[k]; j <= kidsCount[k] + kidsCount[i]; j++) {
				kids[k][j] = kids[i][kidsCount[k] - j];
			}
			kidsCount[k] += kidsCount[i];
		}
	}

	for (int i = 0; i < n; i++) {
		bool ok = true;

		for (int j = 0; j < kidsCount[i]; j++) {
			if (ok == false) {
				i = 0;
				break;
			}
			for (int k = 0; k < kidsCount[kids[i][j]]; k++) {
				if (find(i, kidsCount[i], kids[kids[i][j]][k]) == 0) {
					kids[i][kidsCount[i]] = kids[kids[i][j]][k];
					kidsCount[i]++;
					ok = false;
				}
			}
		}
	}

	int d;
	cin >> d;

	int sum = 0;

	for (int i = 0; i < n; i++) {
		if (d == i) {
			continue;
		}
		if ((kidsCount[i] == 0) && (find(d, kidsCount[d], i) == 0)) {
			sum++;
		}
	}

	cout << sum;
}

fdhyunseo 2년 전 0

어제 DFS를 공부하고 풀었더니 드디어 맞네요. DFS 만세~!

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

문제

문제

출처

ICPC

C++ 시간초과 ㅠㅠ

fdhyunseo 2년 전 0

fdhyunseo 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말