완전탐색 시간초과

안녕하세요 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 등을 만들어야 하기 때문에 해당 함수호출을 많이 해야해서 권장드리지 않습니다.

감사합니다.

아! 더 고민해보다 확인한것이 visited를 사용하면

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

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

조합을 재귀로 구해놓고 풀이하는 방식은 어떻게 접근해야 할까요?

http://boj.kr/ed06ab45e2c24941a1e0c4417f1857c3