파이썬 알고리즘 055 | 최대점수 구하기(DFS) **

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

<내 풀이>

• 자꾸 time이 m을 넘어서는 아이들도 같이 출력됨
  왜냐하면 time==m 이라는 데 도달하면 지금까지 res들 다 같이 출력되니깐=>
  그래서 time>m 이라는 조건 만들었음에도, 저 조건에 도달하면 res들 출력하라고 해놔서
  time이 20넘는 것도 나온다, 또 중복돼서 나오는 것도 있고..===> 어떻게 처리해야 할까

def DFS(x,s,time) : 
    global xx
    if time>m:
        return
    if time==m :
        print(res)
        if sum(res) > xx:
            xx=sum(res)
        return
    else : 
        for i in range(1,n+1) :
            if ch[i]==0:
                ch[i]=1
                res[x]=a[i-1][0]
                DFS(x+1, s+i, time+a[i-1][1])
                ch[i]=0
if __name__=='__main__' :
    a=[]
    n, m = map(int, input().split())
    for _ in range(n) :
        a.append(list(map(int, input().split())))
    xx=0
    ch=[0]*(max(a)[0]+1)
    res=[0]*(n)
    DFS(0,0,0)
    print(xx)

=> else문의 range범위를 잘못 설정했었다, 조합으로 하려면 s,n+1인데..
그런데 고쳤어도, 채점할 값 4,5번에서 인덱스 에러가 난다
File "c:/Users/DONGYUN/Desktop/AA/AA.py", line 14, in DFS
res[x]=a[i-1][0]
IndexError: list assignment index out of range
=====> time==m이 아닌 경우가 존재할 수도 있다, m에 조금 모자랄 수 있음..!
======>어떻게 손봐야 할 지는 모르겠다, 확실히 time==m이 없는 경우도 있을 수 있으니, 저게 출력이 안 될 경우가 존재한다

def DFS(x,s,time) : 
    global xx
    if time>m:
        return
    if time==m :
        print(res)
        if sum(res) > xx:
            xx=sum(res)
        return
    else : 
        for i in range(s,n+1) :
                res[x]=a[i-1][0]
                DFS(x+1, i+1, time+a[i-1][1])
                res[x]=0
if __name__=='__main__' :
    a=[]
    n, m = map(int, input().split())
    for _ in range(n) :
        a.append(list(map(int, input().split())))
    xx=0
    res=[0]*(n)
    DFS(0,0,0)
    print(xx)
    

<풀이>

def DFS(x,s,time) : 
    global res
    if time>m :
        return
    if x==n :
        if s>res:
            res=s
    else : #두가지 경우로 나뉜다. 문제를 푸는 경우와 풀지 않는 경우
        DFS(x+1, s+pv[x] , time+pt[x]) 
        DFS(x+1, s, 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=-1
    DFS(0,0,0)
    print(res)
    

<다른 분들의 풀이>

(1)

def DFS(s, time, score):
    if(time>m):
        return
    global res
    if time<=m:
        if(score>res):
            res=score;
    for i in range(s, n):
        DFS(i+1,time+a[i][1],score+a[i][0])
if __name__ = '__main__' : 
  n, m=map(int, input().split())
  a=[]
  for i in range(n):
      x1,x2 = map(int, input().split())
      a.append((x1,x2))

(2) 조합을 이용한 풀이

def dfs(s, tot, time):
    global grade
    if time > m:
        return
    if tot > grade:
       grade = tot
    for i in range(s, n):
        dfs(i+1, tot+ques[i][0], time+ques[i][1])

n, m = map(int, input().split())
ques = []
for _ in range(n):
    a, b = map(int, input().split())
    ques.append((a, b))
grade = 0
dfs(0, 0, 0)
print(grade)

<반성점>

• 아직도 코드를 짜면서 놓치고 있는 부분이 너무 많다
• 설계를 신중하게 하고 코드를 짜야한다
• 조합을 활용해서 코드를 짠 건데 else 쪽에서 range범위도 이상하게 정하고
• 어렵지 않은 문젠데 자꾸 실패한다

<배운 점>

• 조합으로 이 코드 접근하는 방법 다른 분들거 보고 참고하고 잘 복습하자

< 2회독 내 풀이>

def dfs(x,s,t) :
    global maxx
    if x==n:
        if t<=20:
            if s>maxx:
                maxx=s
    else : 
        dfs(x+1,s+tmp[x][0],t+tmp[x][1])
        dfs(x+1,s,t)
if __name__=='__main__' :
    maxx=-1
    tmp=[]
    n,m=map(int,input().split())
    for i in range(n) :
        a,b=map(int,input().split())
        tmp.append((a,b))
    dfs(0,0,0)
print(maxx)