일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- Bellman-Ford
- codetree
- 마라마라빔
- Kruskal
- programmers
- 장고
- django
- 그리디알고리즘
- 최소스패닝트리
- 함밥
- 백준
- 동적계획법
- 코드트리
- 모각코
- B대면노래방
- 파이썬
- 종합설계
- SQL
- 실습
- Planned
- 알고리즘
- DP
- minimum spanning tree
- 프로그래머스
- DFS
- 소프트웨어공학
- BFS
- 백트래킹
- MyPlaylist
- 데이터베이스
Archives
- Today
- Total
Leta Learns
[Python] 백준 12865번 - 평범한 배낭 본문
문제 https://www.acmicpc.net/problem/12865
냅색 분명히 학교 수업 때 배웠는데 .. 강의 자료 안 보고 하려니까.... 머리에 쥐날 뻔 했다...
어떤 식으로 풀어야 할 지 감이 안 잡혀서 DP테이블 직접 그렸다. 앞으로 DP 문제 풀 때는 테이블 구상하는 방법을 생각해서 접근해야지.
else 부분 max 비교 대상을 찾는 게 관건이었고 그것만 하면 어렵지 않았다.
n, k = map(int, input().split()) #n: 물품의 수, k: 버틸 수 있는 무게
weight = [0 for _ in range(n+1)]
value = [0 for _ in range(n+1)]
dp = [[0 for j in range(k+1)] for i in range(n+1)]
for i in range(1, n+1):
w, v = map(int, input().split()) #w: 각 물건의 무게, v: 해당 물건의 가치
weight[i] = w
value[i] = v
for i in range(1, n+1):
for j in range(1, k+1):
if weight[i] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
print(dp[-1][-1])
'Coding > 백준' 카테고리의 다른 글
[Python] 백준 2606번 - 바이러스 (0) | 2021.07.11 |
---|---|
[Python] 백준 2616번 - 소형기관차 (5) | 2021.07.10 |
[Python] 백준 18234번 - 당근 훔쳐 먹기 (0) | 2021.07.09 |
[Python] 백준 11047번 - 동전 0 (0) | 2021.07.08 |
[Python] 백준 9251번 - LCS (0) | 2021.07.05 |
Comments