[인프런] 최대점수 구하기

문제

• n개의 문제를 풀려고 한다.
• 각 문제는 그 문제를 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어진다.
• 제한시간 m안에 n개의 문제 중 최대점수를 얻을 수 있는 프로그램을 작성하라.
• 단, 해당 시간이 걸리면 푸는걸로 간주하며, 한 유형당 한개만 풀 수 있다.

입력

• n (1 <= n <= 20): 문제의 개수
• m (10 <= m <= 300): 제한 시간
• e.g)
  5 20
  10 5
  25 12
  15 8
  6 3
  7 4

출력

• 최대 점수
• e.g) 41

생각 포인트

• 최대 점수를 얻을 수 있는 방법을 탐색해야하기에 dfs로 구현하자
• 문제를 푸는 경우와 풀지 않는 경우만 존재한다.
  • 따라서 이에 맞는 조건만 재귀함수에 넣어주면 된다.

Solution

n, m = map(int, input().split())
scores = list()
times = list()
sum = 0
ret = -2147000000

for _ in range(n):
    score, time = map(int, input().split())
    scores.append(score)
    times.append(time)


def dfs(level, sum, time_sum):
    global ret
    if time_sum > m:
        return
    if level == n:
        if ret < sum:
            ret = sum
    else:
        dfs(level + 1, sum + scores[level], time_sum + times[level])
        dfs(level + 1, sum, time_sum)


dfs(0, 0, 0)
print(ret)