[코딩테스트][백준] 🔥 백준 7579번 "앱" 문제: Python으로 완벽 해결하기! 🔥

문제링크

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

🛠️ 미해결

• 풀이시간 : 1시간
• 틀린 이유 :
• 0-1 Knapsack 이해 부족 : 0-1 KnapSack 알고리즘에 대해 이해가 부족했다. 오랜만에 다시 풀기도했고... 0-1 KnapSack의 개념 자체는 간단하다 현재 상황에서 물건을 넣을 수 있는지 없는지를 무게로 판단하는 거다. dp의 인수의 값이 중요한데 현재 물건을 넣을 때, 담을 수 있는 가방의 최대 무게에 대해서 최대 가치를 구하는 문제이다. 그렇게 된다면 현재 물건을 더할지 말지가 최대 무게에 따라 정해진다. 만약 현재의 물건의 무게가 가방의 담을 수 있는 최대 무게 즉, 가방의 수용량보다 크다면 담을 수 없기 때문에 현재 물건을 담지 않을 때와 같을 것이다. 만약 그렇지 않고 담을 수 있다면 두 가지 경우로 나누어지는데 넣는 경우와 넣지 않는 경우이다. 넣지 않는 경우에는 전까지의 최대값과 같다고 할 수 있다. 넣는 경우에는 현재 물건을 넣을 수 있는 경우 즉 최대 수용량에서 현재 물건의 무게를 빼고 현재 물건을 넣기전과 같기 때문에 그 값에다가 현재 물건의 가치를 더해주면 된다.

🕒 Python 풀이시간: x

N,M=map(int,input().split())
A=list(map(int,input().split()))
m=list(map(int,input().split()))
result=1e9
A=[0]+A
m=[0]+m

dp=[[0]*(sum(m)+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(0,sum(m)+1):
        nowWeight=A[i]
        nowCost=m[i]
        if j<nowCost:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-nowCost]+nowWeight,dp[i-1][j])
        if dp[i][j]>=M:
            result=min(result,j)
print(result)         

이렇게 Python으로 백준의 "앱" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊