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

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 바둑이 승차-Cut Edge Tech

Cut-Edge Tech를 사용하는 이유

작성

256

이전 문제인 <합이 같은 부분집합>의 경우 전체 합이 짝수일 경우에만 DFS를 호출하도록 작성했습니다.

마찬가지로 이번 바둑이 문제에서도 바둑이 몸무게의 전체 합이 무게 제한에 걸릴 경우에만 DFS를 호출하도록 작성했습니다. 그래서 Time-Exceeded 문제가 발생하는지 모르고 DFS 함수 내에서 Cut-Edge Tech를 적용하지 않았습니다.

혹시 이런 방식으로 조건을 줘서 DFS를 호출하는 것은 잘못된 접근 방식일까요?

답변 2

지식공유자

안녕하세요^^

메인에서 그렇게 위에 처럼 호출하는 것은 그냥 호출하는 것보다는 더 좋아보입니다. 하지만 근본적으로 타임리밋을 해결하는 것은 재귀안에서 컷에지를 통해서입니다.

질문자

<합이 같은 부분집합> 관련해서 추가로 질문 드리고 싶은 것이 있습니다. 그럼 강의에서 설명해 주신 예시 답안에서는 "전체 원소의 합이 홀수일 경우 DFS를 호출하지 않는다"는 내용의 명령어는 없는 게 맞나요?

아래 코드의 경우는 그냥 시간을 단축하기 위한 명렁어인 건가요?

if sum>total//2:
    return

만약 그렇다면 왜 전체 합이 홀수인지 확인하지 않는 건가요?

작성한 질문수