[BOJ/백준 코딩] 평범한 배낭 - PYTHON #12865

소스 코드

# 물품의 수, 무게
n,k = map(int,input().split())

# 물건의 무게
board = [list(map(int,input().split())) for _ in range(n)]
board = [[0,0]] + board

# dp 저장
ans = [[0]*(k+1) for _ in range(n+1)]

for q in range(1,n+1):

    # 무게, 가치
    w,v = board[q]

    for e in range(1,k+1):

        # 현재의 무게보다 작은 무게의 경우
        if w > e:
            ans[q][e] = ans[q-1][e]
            
        # 그 외의 경우
        else:
            ans[q][e] = max(ans[q-1][e-w]+v,ans[q-1][e])

print(ans[-1][-1])

 

---

해결 방법

1. dfs나 bfs 형태로 접근하면 시간 초과 발생

-> dp 선택

 

2. 입력받은 값(w,v)을 기준으로 dp 저장 값을 갱신

 

3. 범위를 n+1하는 이유는 ans[q-1]을 불러올 때, list index 오류 방지하기 위해서, k+1하는 이유는 무게의 값이 1부터 시작하기 때문)

 

ex) tc로 ans(dp 저장 공간)를 진행할 때의 결과물

0	0	0	0	0	0	0	0
0	0	0	0	0	0	max(13+0, 0)	max(13+0, 0)
0	0	0	0	max(8+0, 0)	max(8+0, 0)	max(8+0, 13)	max(8+0, 13)
0	0	0	max(6+0, 0)	max(6+0, 8)	max(6+0, 8)	max(6+0, 13)	max(6+8, 13)
0	0	0	6	8	max(12+0, 8)	max(12+0, 13)	max(12+0, 14)

 

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.