[Python Algorithm] Dynamic programming(동적계획법) - 최대점수 구하기(냅색 알고리즘)

> Dynamic programming(동적계획법)

 

 

 

 

 

📖 문제 : 최대점수 구하기(냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

입력설명

첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

 

출력설명

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

 

 

입력예제 1

5 20
10 5
25 12

15 8 63 74

 

 

출력예제 1

41

 

 

코드

if __name__ == "__main__":

    n, m = map(int, input().split())
    
    dy = [0]*(m+1)
    
    
    for i in range(n):
        point, time = map(int, input().split())
        for j in range(m,time-1,-1):
            dy[j]=max(dy[j-time]+point,dy[j])

    print(dy[m])

 

 

 

Point ! ⭐️

• 이 문제에서는 앞서 2문제들과 다르게 풀 수 있는 문제는 각각 1씩이므로 중복해서 문제를 풀 수 없기에 2차원 리스트를 사용해야한다.
  d[j] = max(dy[i-1][j-pt]+pv의 식을 아래의 이미지와 같이 적용해나가야하는데
  이때 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이기에 실제 코테에서는 이 방법을 사용하다간
  메모리 차지가 너무 심할듯 !! 그래서 1차원 리스트을 사용하되, 중복이 없이 뒤에서부터 탐색해주는 것이다. 
  
  결론은 아래와 같은 이미지의 2차원 리스트로 어떤 식으로 값들이 들어가는지를 이해만 하고, 1차원 리스트를 뒤에서 부터 for문 돌리면서 값을 넣어주기 !

 

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이