[Python]동적계획법2 백준 7579

문제

https://www.acmicpc.net/problem/7579

냅색 문제이다. 이전에 가방안에 넣을수 있는 무게가 정해져있을때 가장큰 가치를 만들수

 있는 경우를 찾아내는 문제로 한번 접해봤다.그때와 같은 방식으로 짜보고 이전 문제는 

가방의 무게가 넘치면 안됬었는데 이번에는 메모리가 초과했을때도 시간만 작다면 채택

할수있게 만들어보자. 

import sys
 
N,M=map(int,sys.stdin.readline().split())
#앱
m=list(map(int,sys.stdin.readline().split()))#메모리
c=list(map(int,sys.stdin.readline().split()))#비활성화 비용
result=[10001]*(M+1)
result[0]=0
#M = 확보할 메모리
for i in range(N):
    rm=m[i]#해당 메모리를 제거할때
    for j in range(M,-1,-1):
        if result[j]!=10001:#해당 값이있다면
            if j+rm>=M:#목표 메모리보다 크다면
                if result[M]>result[j]+c[i]:#기존 보다 비용 더 작게 든다면
                    result[M]=result[j]+c[i]
            else:#목표 메모리보다 작다면
                if result[j+rm]>result[j]+c[i]:#기존보다 비용이 작게든다면 갱신시켜준다.
                    result[j+rm]=result[j]+c[i]
 
print(result[M])

시간초과가 뜨는것을 알 수 있다.pypy3로는 통과되는것을 볼수 있었다.

조건을 보면 메모리의 크기가 1000만까지 가고 배열로 만들어 위 방식을 쓴다면 굉장

히 오래 걸릴것이다.그런데 이문제를 보면 주어지는 앱의 수와 필요시간은 매우 짧은

것을 알수있다.시간을 기준으로 배열을 만들고 해당 메모리값을 넘는것중에서 가장 

짧은 시간이 걸리는걸 고르면 될거같다.

메모리기준이 아닌 시간기준으로 다시짜보자

import sys
 
N,M=map(int,sys.stdin.readline().split())
#앱
m=list(map(int,sys.stdin.readline().split()))#메모리
c=list(map(int,sys.stdin.readline().split()))#비활성화 비용
maxc=sum(c)#비활성화 최대비용
dp=[-1]*(maxc+1)#최대 비용만큼 배열 만들어줌
dp[c[0]]=m[0]#첫번째 값이 0의 시간을 가질경우를 생각못함
dp[0]=0
result=99999999
for i in range(1,N):
    for j in range(len(dp)-c[i]-1,-1,-1):#최대시간에서 줄여가며
        if dp[j]!=-1:
            dp[j+c[i]]=max(dp[j+c[i]],dp[j]+m[i])
            if dp[j+c[i]]>=M:
                result=min(result,j+c[i])
 
 
print(result)

해당코드는 첫번째 값을 초기화하는 코드를 넣는 바람에 에러가 난경우이다.

처음에 0의 비용을 가지는 앱이 올수있는 경우에 틀릴것이다.

첫번째 값을 따로 처리 하지않고 결과값또한 저렇게 하는거보다 시간순으로 돌렸을때 

더욱 빠르게 찾아낼것이다.

마지막으로 조금 깔끔하게 수정하여보자.

import sys
 
N,M=map(int,sys.stdin.readline().split())
#앱
m=list(map(int,sys.stdin.readline().split()))#메모리
c=list(map(int,sys.stdin.readline().split()))#비활성화 비용
maxc=sum(c)+1#비활성화 최대비용
dp=[-1]*(maxc)#최대 비용만큼 배열 만들어줌
dp[0]=0
for i in range(N):
    for j in range(maxc-c[i]-1,-1,-1):#최대시간에서 줄여가며
        if dp[j]!=-1:#이전에 만들었던 값이 있다면
            dp[j+c[i]]=max(dp[j+c[i]],dp[j]+m[i])
 
 
for i in range(maxc):
    if dp[i]>=M:#가장 작게 드는 비용을 찾았다면 출력
        print(i)
        break

다음에 이런 문제가 나오면 더 작은 범위의 값들을 활용해 답을 찾을수 있는방법을 

먼저 생각해봐야겠다.요즘 문제를 풀고 피드백하는시간이 점점 길어지고있다.

문제를 풀거나 피드백 할때 조금더 집중해야될거같다.