최대점수 구하기(DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/aaLB

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

내 풀이 (정답 아님)

#내 풀이
def DFS(L, sum, time):
    global res
    if total-sum < res-sum:
        return
    if L == n:
        if time <= m:
            if sum > res:
                res = sum
    else:
        for i in range(n):
            DFS(L+1, sum+s[i], time+t[i])
            DFS(L+1, sum, time)

if __name__ == "__main__":
    s = []
    t = []
    n, m = map(int, input().split())
    for i in range(n):
        a, b = map(int, input().split())
        s.append(a)
        t.append(b)

    total = sum(s)

    res = -2147000000
    DFS(0, 0, 0)
    print(res)

예제는 통과했는데 채점기를 돌려보니 시간초과가 발생했다.

 

강의 풀이

#강의 풀이
def DFS(L, sum, time):
    global res
    if time > m:
        return
    if L == n:
        if sum > res:
            res = sum
    else:
        DFS(L+1, sum+pv[L], time+pt[L])
        DFS(L+1, sum, time)

if __name__ == "__main__":
    n, m = map(int, input().split())
    pv = list()
    pt = list()
    for i in range(n):
        a, b = map(int, input().split())
        pv.append(a)
        pt.append(b)
    res = -2147000000
    DFS(0, 0, 0)

 

머릿속에 DFS가 정리가 제대로 안된듯하다

나는 쓸데없는 for문을 돌렸다