최대점수 구하기(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

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(idx, score_sum, time_used):
    global max_score
    if time_used > M:
        return
    if score_sum + sum(scores[idx:]) < max_score:
        return
    if idx == N:
        if score_sum > max_score:
            max_score = score_sum
    else:
        DFS(idx+1, score_sum+scores[idx], time_used+durations[idx])
        DFS(idx+1, score_sum, time_used)


if __name__ == "__main__":
    N, M = map(int, input().split())
    max_score = 0
    scores = []
    durations = []
    for _ in range(N):
        a,b = map(int,input().split())
        scores.append(a)
        durations.append(b)
    DFS(0,0,0)
    print(max_score)

 

모범답안

#모범답안
import sys
sys.stdin = open("input.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)

 

느낀점

1. 바둑이 승차 응용이구나

2. DFS 가지 여러개인 for문 돌리는거 풀다가 다시 부분집합 구하는 문제..
즉, 상태트리의 가지수가 포함한다 안한다 두 개인 문제를 풀려니 좀 헷갈렸다.. 바보!!!!
여러번 반복해서 풀면서 척하면 척하고 적용하는 방법밖에 없구나..
얼른 한번 싹 보고 양치기로 문제 양을 많이 풀어봐야겠다.

3. 모범답안은 내 가지치기 기준 세개 중 두개만 사용했는데,
남은 점수의 합이 이미 최댓값보다작으면 그냥 리턴해버리는 가지치기 없이도
시간제한에 안걸렸나부다. 하여튼 초반에 좀 헤맸지만 잘 해냈당!

---

 

다시 풀어보기

#다시
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(idx, score, time):
    global max_score
    if time > M:
        return
    if score+sum(scores[idx:]) < max_score:
        return
    if idx == N:
        if score > max_score:
            max_score = score
    else:
        DFS(idx+1,score+scores[idx], time+times[idx])
        DFS(idx+1, score, time)

if __name__=="__main__":
    N, M = map(int, input().split())
    scores = []
    times = []
    for _ in range(N):
        a, b = map(int,input().split())
        scores.append(a)
        times.append(b)
    max_score = 0
    DFS(0,0,0)
    print(max_score)