서버 업그레이드 예산 배분

문제

사내 인프라팀이 노후 서버를 업그레이드하려고 합니다. 부품 벤더가 보내온 견적서에는 업그레이드 가능한 부품 옵션들이 한 줄씩 나열되어 있습니다. 각 옵션은 [part, cost, score] 형태로, part는 부품 종류(예: "CPU", "RAM", "SSD"), cost는 구매 비용, score는 장착 시 얻는 성능 점수입니다.

같은 부품 종류에는 여러 등급의 옵션이 있을 수 있지만, 서버에는 부품 종류마다 슬롯이 하나뿐 이므로 같은 part의 옵션은 최대 1개 만 선택할 수 있습니다. 어떤 부품 종류는 아예 업그레이드하지 않고 건너뛰어도 됩니다.

총 지출이 budget을 넘지 않도록 옵션을 골랐을 때, 얻을 수 있는 성능 점수 합의 최댓값을 반환하세요. 아무것도 선택하지 못하면 0을 반환합니다.

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

예시

budget=10, options=[["CPU",5,8],["CPU",7,12],["RAM",3,5],["SSD",4,6]] → 17
  (CPU 7원짜리(12점) + RAM 3원짜리(5점) = 지출 10, 점수 17.
   CPU 옵션 2개를 동시에 살 수는 없다)
 
budget=4, options=[["CPU",5,10],["RAM",6,9]] → 0
  (예산 안에 살 수 있는 옵션이 하나도 없음)
 
budget=7, options=[["CPU",3,5],["CPU",5,9],["RAM",4,6],["NIC",2,3]] → 12
  (CPU 5원(9점) + NIC 2원(3점) = 지출 7, 점수 12. RAM은 건너뜀)

제약 조건

• 0 ≤ budget ≤ 10,000
• 1 ≤ options.length ≤ 200
• options[i] = [part, cost, score]
  • part: 길이 1~10의 영문 대문자/숫자 문자열, 서로 다른 part 종류는 최대 50개
  • 1 ≤ cost ≤ 10,000 (정수)
  • 1 ≤ score ≤ 10,000 (정수)
• 같은 part의 옵션은 최대 1개만 선택할 수 있고, 선택하지 않는 part가 있어도 된다.

시간 복잡도 목표: O(N · budget) (N = 옵션 개수)