[Python Algorithm] 깊이/넓이 우선탐색(DFS, BFS) - 최대점수 구하기(DFS)

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (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

 

 

 

import sys
input = sys.stdin.readline

def DFS(L, sum, t):
  global res
  if t > m:
    return
  if L==n:
    if sum > res:
      res = sum
  else:
    DFS(L+1, sum+point[L], t+time[L])
    DFS(L+1, sum, t)
  

n , m = map(int, input().split())

point = list()
time = list()

for i in range(n):
  a, b = map(int, input().split())
  point.append(a)
  time.append(b)

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

 

⭐️ Point ! ⭐️

• 여기서 가지는 L = 0은 첫 문제, L=1은 두번째 문제 이런식으로 OX 두가지의 가지로 뻗어 나가면서 그 값들을 넣을지 안넣을지로 판단

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이