.PNG)
79. 최대점수 구하기(냅색 알고리즘)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를
풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩
니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는
해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4
▣ 출력예제 1
41
<내 풀이>
(1) 처음에 이렇게 풀었는데 이거는 앞에 문제들과 달리 문제를 한번만 풀면 끝이기 때문에 앞 문제들과 똑같이 접근하면 안됨
n,m=map(int,input().split())
dy=[0]*(m+1)
for i in range(n) :
s,t = map(int, input().split())
for j in range(t,m+1):
dy[j]=max(dy[j],dy[j-t]+s)
print(dy)
print(dy[m])(2) 문제가 한번씩만 계산되게 해야한다 - 어떻게 해야할까......
=> 1차 리스트 만들어서 역순으로 (m, pt-1,-1) m부터 pt까지 거꾸로 순서로.. <풀이 듣고 구현>
n,m=map(int,input().split())
dy=[0]*(m+1)
for i in range(n) :
pv,pt=map(int,input().split())
for j in range(m,pt-1,-1) :
dy[j]=max(dy[j], dy[j-pt]+pv)
print(dy[m])
<풀이>
(1) 2차리스트 이용 => 그러나 too much memory
- dy테이블을 2차 리스트로 만든다 (행은 n+1 (문제의 갯수 0~5),열은 m+1(0~20)
- dy[3][15] -> 세번째 문제까지 풀었을 때 주어진 시간이 15분
- 참조할 때 dy[i-1][j-pt] 번째를 참조해주기 (겹치지 않게 하기 위해서)
(2) 1차리스트 사용, 역순으로 넣어주기
뒤에서부터 앞으로 점수 매기면 중복될 일이 없다
코드를 입력하세요
<반성점>
- 거꾸로 넣어주는 방법도 존재함
<배운 점>
- 하나씩만, 중복 없이 진행될 때는 2차리스트로 만들어준다 => 근데 이거 메모리 많이 들어서 1차리스트로 처리해주되, 역순으로 넣어주면 된다
<2차 내 풀이>
n,m=map(int,input().split())
k=[]
for i in range(n) :
s,t=map(int,input().split())
k.append((s,t))
dy=[0]*(m+1)
for i in range(n) :
for j in range(m,k[i][1]-1,-1) :
dy[j]=max(dy[j],dy[j-k[i][1]]+k[i][0])
print(max(dy))