글 읽기 - [c++] 왜 시간초과가 나는지 모르겠습니다..

(追記) (追記ここまで)

[c++] 왜 시간초과가 나는지 모르겠습니다..

11378번 - 열혈강호 4

tizm423 4년 전 0

이분매칭을 생각해서 풀어봤습니다.

문제가 되는 부분은 45번줄부터 시작하는 중첩for문인데

시간초과가 날 이유가 없다고 생각합니다.

혹시 제가 뭘 놓치고 있는걸까요??

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
vector<int> adj[1000];
int matched[1001];
bool visited[1000];
bool dfs(int a){
	if(visited[a]) return false;
	visited[a] = true;
	for(int b : adj[a]){
		if(matched[b] == -1 || dfs(matched[b])){
			matched[b] = a;
			return true;
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for(int i=0; i<N; i++){
		int count;
		cin >> count;
		while(count--){
			int num;
			cin >> num;
			adj[i].push_back(num);
		}
	}
	
	int count = 0;
	fill(matched, matched+M+1, -1);
	for(int i=0; i<N; i++){
		fill(visited, visited+N, false);
		if(dfs(i)) count++;
	}
	
 // 문제가 되는 부분
	int L = K;
	for(int j=0; j<L; j++){
		for(int i=0; i<N; i++){
			fill(visited, visited+N, false);
			if(dfs(i) && K) {
				count++;
				K--;
				break;
			}
		}
	}
	cout << count << "\n";
}

djm03178 4년 전 1

그 부분이 루프를 이중으로 돌기 때문에 O(N^2)인데, dfs 한 번 할 때마다 visited를 초기화하므로 O(N^2) 시간이 걸려서 총 O(N^4) 시간이 걸립니다.

tizm423 4년 전 0

아하.. 그래서 중간에 빠져나와야 시간안에 답을 받을 수 있던거군요!!

답변 감사드립니다!!ᄒᄒ

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

[c++] 왜 시간초과가 나는지 모르겠습니다..

tizm423 4년 전 0

djm03178 4년 전 1

tizm423 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말