-
12865. [Python]평범한 배낭Python_알고리즘/Gold V 2024. 6. 5. 01:27
1. 문제
https://www.acmicpc.net/problem/12865
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 512MB
- DP(다이나믹 프로그래밍)
3. 파이썬 코드
import sys input = sys.stdin.readline N, K = map(int,input().split()) # 가방 bag = [] # weight, value 값 가방에 저장 for _ in range(N): weight, value = map(int,input().split()) bag.append((weight,value)) # dp 값을 K(무게) +1 만큼 생성 dp = [0] * 100001 # N개의 물건 개수만큼 반복 for i in range(N): # weight, value 값 분해 w, v = bag[i] # 끝에서부터 반복문 진행 for j in range(K,w-1,-1): # 이미 가방에 값이 있는경우 그 값과 그 값에서 weight 뺀 무게 + value 값중 큰 값으로 갱신 # 여기서 끝에서부터가 아닌 weight 값부터 시작할 경우 의도치 않은 갱신이 발생하기 때문에 큰값에서 -1 씩 해나감 dp[j] = max(dp[j], dp[j-w]+v) print(dp[K])
4. 문제를 풀고난 후 생각
- 전형적인 DP 문제로 TOP-DOWN 방식으로 문제를 해결함
- 그 무게에서 value 비중이 가장 높은 값을 갱신해 나가는 구조로 반복문을 진행하며 값을 갱신해줌
5. 문제를 푸는데 도움이 되는 지식
- DP(다이나믹 프로그래밍)
'Python_알고리즘 > Gold V' 카테고리의 다른 글
5972. [Python]택배 배송 (0) 2024.06.20 9251. [Python]LCS (0) 2024.06.16 13549. [Python]숨바꼭질 3 (0) 2024.05.22 14284. [Python]간선 이어가기 2 (0) 2024.05.08 7569. [Python]토마토 (0) 2024.04.25