안녕 - 실버 4 (백준, DP)
2023. 1. 13. 22:08ㆍ코딩 테스트 준비
728x90
반응형
N = int(input())
L = [int(x) for x in input().split()]
J = [int(x) for x in input().split()]
L, J = [0] + L, [0] + J
dp = [[0 for _ in range(101)] for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, 101):
if L[i] <= j:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]] + J[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[N][99])https://gsmesie692.tistory.com/113?category=523232
Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)
도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서
gsmesie692.tistory.com
이런 식의 문제를 배낭 채우기 문제라고 하는 걸 처음 알았다. 공부해두자!
728x90
반응형
'코딩 테스트 준비' 카테고리의 다른 글
| 경로 찾기 - 실버 1 (백준, DFS) (0) | 2023.01.15 |
|---|---|
| 회의실 배정 - 실버 1 (백준, 그리디) (0) | 2023.01.15 |
| 숨박꼭질 2 - 골드 4 (백준, BFS) (0) | 2023.01.13 |
| 주몽 - 실버 4 (백준, 투포인터) (0) | 2023.01.13 |
| 예산 - 실버3 (백준, 이분탐색) feat. 이분탐색 (0) | 2023.01.13 |