목록2026/01/26 (1)
cmod.ify
[12865] 평범한 배낭
1차원 DP 배열의 변화 원리1. 핵심 규칙: 뒤에서부터 채우기1차원 배열을 앞에서부터 채우면, 방금 업데이트한 값을 같은 물건에서 또 참조하게 되어 '물건 중복 담기' 오류가 발생함. 하지만 뒤에서부터 채우면 dp[j-w]는 아직 '이전 물건까지만 계산된 값'을 유지하고 있으므로 2차원 배열의 dp[i-1][j-w]와 똑같은 효과를 냄.2. 예시 상황 재현배낭 용량: 7물건 A: 무게 4, 가치 8물건 B: 무게 3, 가치 6[Step 1] 물건 A (4, 8) 처리j를 7부터 4까지 줄이며 계산함.dp[7] = max(0, dp[7-4]+8) = 8dp[6] = max(0, dp[6-4]+8) = 8dp[5] = max(0, dp[5-4]+8) = 8dp[4] = max(0, dp[4-4]+8) = ..
BASIC/코딩테스트
2026. 1. 26. 18:35