인프런 커뮤니티 질문&답변

if (sum > c || sum < answer) return;

이거 말씀하시는듯

미리 정렬한다는 말은 dfs를 돌리기전에 바둑이를 [81,61,58,42,33] 으로 정렬하고 하나씩 더해간다는 말입니다.

그럼 큰수부터 더해나가니깐 max에 더 빨리 도달하므로 정렬되지 않았을때보다 dfs를 덜 호출하므로 정렬하는게 낫지않을까 라는 질문이었습니다:) 

안녕하세요^^

미리 정렬하고 DFS를 돌리면 한 번만에 나온다는게 뭔지 모르겠네요. 어자피 DFS를 돌려야 하는데....

재귀를 시간복잡도 단축하는 방법은 컷에지 방식을 주로 씁니다. 답이 나오지 않을 가지를 미리 예측해서 뻗어나가지 않는 방식입니다. 영상에서는 설명하지 않았지만 제가 제공한 소스코드에 보시면 아래와 같은 코드가 추가되어 있습니다. 이 코드를 하면 컷에지가 되어 많이 단축됩니다.

if(sum+(total-tsum)<answer) return;