[알고리즘] 최대점수 구하기(DFS)

(문제) 최대점수 구하기(DFS)

---

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

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

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
(해당문제는해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입력설명

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

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

출력설명

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

테스트케이스

입력예제	출력예제
5 20 10 5 25 12 15 8 6 3 7 4	41
9 50 12 7 16 8 20 10 30 15 10 5 25 12 15 8 6 3 7 4	101
12 70 5 2 11 5 12 7 16 8 20 10 30 15 10 5 25 12 15 8 6 3 7 4 3 2	141

---

해결방법

방법 1) 매개변수를 이용하여 접근 dfs (추가 리스트 구축 안함)

1. 입력으로 들어오는 n의 값과 m의 값을 분리
2. 2번째 줄 부터는 리스트 정규식을 이용하여 split를 사용하여 리스트로 각각 n 만큼 반복하여 a라는 리스트를 만들기
3. 최대 점수를 저장할 max라는 변수를 정의 (초기화를 작은 값을 하기 위해서 임의로 -2170으로 했다)
4. dfs를 이용하여 dfs()함수를 인자 x(깊이), score(성적), time(시간) 순으로 읽을 수 있게 만든다.
5. 만약 n만큼의 깊이가 아닐 경우, dfs(x+1, score + a[x][0], time + a[x][1])로 접근 했을 때의 경우의 수를 생각한다.
6. 해당 함수 밑에는 만약 n만큼의 깊이가 아닐 경우, dfs(x+1, score, time )로 접근하지 않았을 경우라는 경우의 수 만든다.
7. x가 n만큼의 깊이를 돌 때, 가지고 있는 매개변수 score이랑 time의 값을 비교한다.
8. 만약 x가 n이고, 매개변수로 받은 time의 값이 m 보다 작거나 같고, max에 할당 되어있는 값이 score의 값보다 작을 경우 max에 score의 값을 대입한다.

방법 2) 리스트를 만들어 dfs

1. 입력으로 들어오는 n의 값과 m의 값을 분리
2. 2번째 줄 부터는 리스트 정규식을 이용하여 split를 사용하여 리스트로 각각 n 만큼 반복하여 a라는 리스트를 만들기
3. 최대 점수를 저장할 max라는 변수를 정의 (초기화를 작은 값을 하기 위해서 임의로 -2170으로 했다)
4. x가 n만큼의 깊이를 돌 때, 비교할 수 있는 score라는 빈 리스트와 time이라는 빈 리스트 생성.
5. dfs를 이용하여 dfs()함수를 인자 x(깊이) 로 함수를 정의.
6. 만약 n만큼의 깊이가 아닐 경우, score라는 리스트와 time이라는 리스트에 각각 a[x][0], a[x][1]을 삽입한다.
7. 그 후, dfs(x+1)로 접근 했을 때의 경우의 수를 생각한다.
8. 첫 dfs(x+1)이 끝나면 score랑 time을 각각 pop() 시킨 후, 각 요소가 없었을 경우를 생각한다.
9. x가 n만큼의 깊이를 돌 때, 가지고 있는 time 리스트의 요소 값들의 합이 m 을 넘지 않거나 같고, max에 할당 되어 있는 값이 score 리스트 요소 값들보다 작을 경우 max에 해당 score 리스트 요소의 값을 전부 더한 값을 할당한다.

---

코드

방법 1) 매개변수를 이용하여 접근 dfs (추가 리스트 구축 안함)

def dfs(x, score, time):
    global _max
    if x == n:
        if  time <= m:
            if _max < score:
                _max = score
    else:
        dfs(x+1, a[x][0] + score, a[x][1] + time)
        dfs(x+1, score, time)

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

a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[0], reverse=True)


_max = -2170

dfs(0, 0, 0)

print(_max)

방법 2) 리스트를 만들어 dfs

def dfs(x):
    global _max
    if x == n:
        if sum(time) <= m:
            if _max < sum(score):
                _max = sum(score)
    else:
        score.append(a[x][0])
        time.append(a[x][1])
        dfs(x+1)
        score.pop()
        time.pop()
        dfs(x+1)

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

a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[0], reverse=True)

score = []
time = []

_max = -2170

dfs(0)

print(_max)