[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

 

나의 코드

def DFS(L,PointS,TimeS):
    global M
    if TimeS>m:
        return

    if L==n:
        if PointS>M:
            M=PointS
    else:
        DFS(L+1,PointS+arr[L][0],TimeS+arr[L][1])
        DFS(L+1,PointS,TimeS)

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

arr=[]

for _ in range(n):
    a,b=map(int,input().split())
    arr.append([a,b])
M=0
DFS(0,0,0)

print(M)

 

처음 조합을 사용하는 문제로 생각해 접근했지만 출력될수 있는 선택가지가 여러개이므로 조합으로 접근을 하지 않았따.

입력값 하나 하나를 더하냐? 더하지 않냐고 완전 탐색을 진행하였다.

또한 DFS의 인자를 L(레벨)하나만 가진채 체크리스트로 선택의 유무를 모두 탐색하여 조사한뒤 점수의 합과 시간의 합을 계산하여 답을 구하려였지만 그러면 cut-edge를 하지 않아 시간 오바가 날것 같아 인자 3개를 사용해여 이미 시간이 m을 초과한 경우는 탐색을 하지 않게 하였다.

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
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)

리스트를 하나가 아닌 두개로 둔점 이외엔 똑같다 !