백준 7579 - 앱 (Python)

https://acmicpc.net/problem/7579 

7579번: 앱

다른 문제보다 빠르게 원트에 풀 수 있었던 문제였다. 보고 바로 냅색 문제임은 생각할 수 있었다.

다만 비용을 기준으로 정렬할지 메모리를 기준으로 정렬할지를 잠시 고민했다.

비용의 범위가 더 좁아 비용을 이용해 냅색을 진행했다. cost를 다 합한 것을 dp의 길이로 설정했다.

n,m=map(int,input().split())
m_lis=list(map(int,input().split())) #메모리 리스트
c_lis=list(map(int,input().split())) #비용 리스트
dp=[0]*(sum(c_lis)+1) #특정 비용에서의 최소의 메모리 이용 비용 저장

for i in range(n):
    memory = m_lis[i]
    cost = c_lis[i]
    for j in range(len(dp)-1,cost-1,-1):
        if dp[j]<dp[j-cost]+memory:
            dp[j]=(max(dp[j-cost]+memory,dp[j]))

for i in range(len(dp)):
    if dp[i]>=m:
        print(i)
        exit(0)

이 과정을 거칠 때, 이중 for문에서 안에 있는 것을 순방향으로 해서는 안 된다는 점을 기억해야 한다.

순방향으로 했다가는 업데이트를 한 번 한 것을 다시 해버리게 될 수 있다.