Algorithm - 최대점수 구하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[최대점수 구하기(DFS)]

 

현수는 선생님이 주신 N개의 문제를 풀려고 한다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어져있다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 하는 프로그램을 작성하시오. 

(단, 해당문제는 해당시간이 걸리면 풀리는 것으로 간주하며 한 유형당 한 개의 문제만 풀 수 있음)

 

 

*입력 설명

첫 번째 줄에 문제의 개수 N(1 ≤ N ≤ 20)과 제한시간 M(10 ≤ M ≤ 300)이 주어진다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어진다.

 

*출력 설명

첫 번째 줄에 제한시간 내에 얻을 수 있는 최대점수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_56.txt', 'rt')

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)
    print(res)
    
# 출력 : 41

 

input_56.txt(입력)

5 20
10 5
25 12
15 8
6 3
7 4

 

 

중요내용

1. 변수 pv는 문제의 점수를 저장하는 리스트이다.
2. 변수 pt는 문제풀이 시간을 저장하는 리스트이다.
3. DFS() 함수의 인자 L, sum, time은 각각 상태트리의 레벨, 최대점수, 문제풀이 총시간을 뜻한다.
4. DFS(L+1, sum+pv[L], time+pt[L]) 코드는 다음 문제를 푸는 경우를 의미한다.
5. DFS(L+1, sum, time) 코드는 다음 문제를 풀지 않고 넘어가는 경우를 의미한다.
6. 변수 res는 최대점수(최대값)를 구하기 위해 사용되는 변수이다.