파이썬 알고리즘-54 (DFS/BFS 활용) 최대점수 구하기

54.최대점수 구하기(DFS)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를
풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩
니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는
해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4

▣ 출력예제 1
41

내 코드

def dfs(t, s, sum):
    global score
    if t >= m or (t<m and sum==total):
        if t == m:
            if score < sum:
                score = sum
        elif t>m:
            sum -= lst[s-1][0]
            if score < sum:
                score = sum
                
        elif t<m:
            if score<sum:
                score=sum 
    else:
        for i in range(s, n):
            dfs(t+lst[i][1], i+1, sum+lst[i][0])

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
score = 0
total=sum([i[0] for i in lst])
dfs(0, 0, 0)
print(score)

부분집합을 구하는 것처럼 모든 경우의 수를 구하면서, 합이 최대인 것을 찾고자 했다. 시간의 합이 제한시간보다 크거나 같을 때, 또는 제한시간보다 작으면서 점수의 합이 전체 합과 같을 때로 나누어 최대합을 찾았다.

풀이

def dfs(s, sum, t):
    global score
    if t>m:
        return
    if sum>score:
        score=sum
    for i in range(s, n):
        dfs(i+1, sum+lst[i][0], t+lst[i][1])

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
score = 0
dfs(0, 0, 0)
print(score)

반성점

• 가지치기 할 때 쓸데없는 조건을 너무 많이 설정했다. 시간의 합이 제한시간보다 크면 무조건 리턴해도 문제 없었는데 이를 간과했다.

배운 것