완전탐색 시간초과

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-A

작성

629

안녕하세요 큰돌님

덕분에 알고리즘을 재미있게 공부하고 있습니다!

질문사항이 있는데요

완전탐색으로 풀이를 해보았는데 시간초과가 났습니다.

그래서 방법을 바꿔 visited를 사용하지 않고 풀어보았는데 통과했습니다.

시간초과가 발생한 정확한 이유를 모르겠어서 디버깅을 해보았는데 두코드간의 함수호출 횟수가 분명 차이가 있었습니다.

하지만 그 원리를 이해하지 못해서 질문드립니다.

디버깅을 하면 할수록 머리가 더 복잡해지는것 같습니다...

시간초과 코드

http://boj.kr/9ca3908dd4624835a28aca2db266321e

정답 코드

http://boj.kr/18bd16121a7d46ada6f06e4313594796

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 sol님ㅎㅎ

1, 2, 3 그리고 1, 3, 2처럼 중복이 발생해서 시간초과가 나는것이 맞나요?

>>그게 아니구요.

자 맞았습니다. 받은 코드를 볼게요.

	vec.push_back(idx);
	dfs(idx + 1, p + fd[idx].protine, f + fd[idx].fet, t + fd[idx].tan, v + fd[idx].vitamin, sum + fd[idx].price);
	vec.pop_back();
	dfs(idx + 1, p, f, t, v, sum);

지금 보시는 것처럼 추가 또는 추가 하지 않는다. 를 idx + 1을 해가며 가는 것을 볼 수 있죠? 앞의 코드는 for문이 없습니다. 1 >> 2 >> 3 이렇게 정갈하게 idx가 증가되며 모든 경우의 수 2 ^ n을 확인하니까요.

근데 이 코드를 볼까요?

매번.

매번. for문으로 모든 식품들을 탐색해나갑니다.

	for(int i = 1; i <= N; i++){
		if(!visited[i]){
			visited[i] = 1;
			vec.push_back(i);
			dfs(p + fd[i].protine, f + fd[i].fet, t + fd[i].tan, v + fd[i].vitamin, sum + fd[i].price);
			vec.pop_back();
			visited[i] = 0;
		}
	}

그렇기 때문에 시간초과가 뜨는 것 같습니다.

그래서 코드를 바꿔 조합을 재귀로 활용하여 풀어보려고 했는데 27%에서 틀렸다고 나옵니다

>> 해당 부분 코드 확인했는데요. 일단 combi함수로 이 문제를 풀기에는 어렵습니다. 왜냐면 combi 함수 자체는 nCm 정도를 만드는 것이라서요. 즉 이걸 기반으로 nC1 nC2 등을 만들어야 하기 때문에 해당 함수호출을 많이 해야해서 권장드리지 않습니다.

감사합니다.