[BOJ] 12865번 평범한 배낭 / 사용언어 : 파이썬(python)

※ 문제링크 

12865번: 평범한 배낭

※ 관련개념 및 참고사이트

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

해당 문제는 Knapsack 알고리즘과 DP를 활용하여 풀어야하는 문제였다. 처음에는 조건문과 반복문으로 해결해보려하였으나, 실패하여 구글링을 통해 문제를 해결해보았다. 구글링 도중 Knapsack알고리즘을 활용하여 풀어야한다고 하여 개념만 이해하고 구현은 직접 해보려고 시도하였다. 그 중에서 Knapsack알고리즘에 대해 이해하기 쉽게 설명하고 있는 사이트가 있어서 링크를 걸어두었으니 이해가 잘 안되는 사람들은 참고하면 좋을 것 같다. 다만 DP와 Knapsack 알고리즘으로 풀었음에도 코드 자체가 시간이 오래 걸려서 그런지 Python3로는 시간초과가 뜨고, PyPy3로만 통과가 가능하였다. 해당 부분은 추후 한번 더 풀어보며 시간단축을 시도해볼 생각이다. 풀이방법과 코드는 아래와 같다.

1. 입력값으로 받은 물건의 개수와 가치를 2차원 리스트로 작성한다.

2. 반복문을 돌려 DP리스트에 값을 채운다.

3. 중간중간에 value값보다 큰 가치를 가지는 경우가 발생하면 value를 갱신하고 반복문이 끝난 후 value값을 출력한다.

 

N, W = map(int, input().split())
p_list = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
value = 0
for i in range(N):
    for k in range(W+1):
        if k >= p_list[i][0]:
            dp[i+1][k] = max(dp[i][k-p_list[i][0]] + p_list[i][1], dp[i][k]) 
        else:
            dp[i+1][k] = dp[i][k]
        if value < dp[i+1][k]:
            value = dp[i+1][k]
print(value)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.