#090 · DP어려움DP / 0-1 배낭

예산 한도 장바구니

문제

온라인 쇼핑몰에서 N개의 상품을 장바구니 후보로 골랐습니다. i번째 상품의 가격은 costs[i], 그 상품을 담았을 때 얻는 만족도는 values[i] 입니다. 사용할 수 있는 총 예산은 budget 입니다.

각 상품은 0개 또는 1개만 담을 수 있습니다. (쪼개거나 여러 개 담을 수 없음) 담은 상품들의 가격 합이 budget 을 넘지 않도록 하면서, 만족도 합이 최대가 되도록 골랐을 때의 만족도 합 최댓값을 반환하세요.

solution(costs, values, budget) 형태로 구현합니다.

예시

costs=[3,4,5], values=[4,5,6], budget=7   → 9
  (가격 3+4=7 ≤ 7, 만족도 4+5=9. 5+? 는 예산 초과로 단일뿐)
costs=[2], values=[10], budget=1          → 0
  (유일한 상품 가격 2 > 예산 1, 아무것도 못 담음)
costs=[1,2,3], values=[6,10,12], budget=6 → 28
  (전부 담아도 가격 합 6 ≤ 6, 만족도 6+10+12=28)

제약 조건

1 ≤ N ≤ 100
1 ≤ costs[i] ≤ budget ≤ 1000
1 ≤ values[i] ≤ 10000
costs.length === values.length === N

시간 복잡도 목표: O(N · budget)

테스트 케이스

예시 1: 3+4 담아 만족도 9

입력: costs = [3,4,5], values = [4,5,6], budget = 7

출력: 9

예시 2: 예산 부족으로 0

입력: costs = [2], values = [10], budget = 1

출력: 0

예시 3: 전부 담기 → 28

입력: costs = [1,2,3], values = [6,10,12], budget = 6

출력: 28

엣지: 아이템 1개 딱 맞게 담기

입력: costs = [5], values = [7], budget = 5

출력: 7

가성비 선택: 6+4 → 30+16=46

입력: costs = [6,3,4,2], values = [30,14,16,9], budget = 10

출력: 46

고전 배낭: 20+30 → 100+120=220

입력: costs = [10,20,30], values = [60,100,120], budget = 50

출력: 220

동일 아이템: 2개만 담김 → 10

입력: costs = [4,4,4,4], values = [5,5,5,5], budget = 10

출력: 10

복합: 9+5+6 가격합 20 → 13+6+8=27 (최적)

입력: costs = [7,8,9,5,6], values = [9,11,13,6,8], budget = 20

출력: 27

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.