[코딩테스트][백준] 🔥 백준 12865번 "평범한 배낭" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

def knapsack(k,wt,val,n):
    global dp
    for i in range(n+1):
        for j in range(k+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif wt[i-1]<=j:
                dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    return dp[n][k]

n,k=map(int,input().split())
wt=[]
val=[]
for i in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    val.append(v)
dp=[[0]*(k+1) for _ in range(n+1)]
print(knapsack(k,wt,val,n))
    

0-1 Knapsack의 기본적인 유형이다.

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