Inflearn Community Q&A

요즘 강사님의 DFS 강의의 매력에 푹 빠져있습니다.

바둑이승차 관련 Cut-Edge Tech의 다른 방법에 대해 고민해보았습니다.  List 슬라이싱을 활용한 방법입니다. 아이디어는 강사님의 것과 같습니다.

본 강의의 다음 부분을 

if sum+(total-tsum)<result:

     return

아래와 같은 방법으로 접근하였습니다.

if sum+sum(inList[L+1:])<result:

return

하지만 결과적으로 Case#2 실패하여 채점프로그램에서 80점을 받았습니다. 이 방식이 강사님의 방식과 논리적으로 차이가 나는 부분이 있는지 알고 싶습니다.

import sys
sys.stdin = open("input", "rt")


def DFS(L, sumN):
    global maxN
    if sumN + sum(inList[L+1:]) < maxN:
        return
    if sumN > C:
        return
    if L == N:
        if sumN > maxN:
            maxN = sumN
    else:
        DFS(L+1, sumN+inList[L])
        DFS(L+1, sumN)


if __name__ == "__main__":
    C, N = map(int, input().split())
    inList = [0]*N
    for i in range(N):
        inList[i] = int(input())
    inList.sort(reverse=True)
    maxN = -2147000000
    tot = sum(inList)
    DFS(0, 0)
    print(maxN)