본문 바로가기

알고리즘

POS기의 묶음 할인

New Era · 13번Lv. 3동적 계획법

POS기의 묶음 할인

문제 설명

대리인 No.1의 기록 중에서

(주)캣네생선의 판매량이 늘자 "계산이 틀렸다냥!" 하는 민원이 이어졌습니다. 대리인 No.1은 길게 보면 모든 냥이에게 수학을 가르쳐야 한다고 생각했지만, 당장은 생선가게마다 POS기를 보급하기로 했습니다.

그런데 가게에는 낱개 가격 말고도 '광어 2마리 + 갈치 1마리' 같은 묶음 상품이 있습니다. 손님은 언제나 가장 싸게 사고 싶어 하므로, POS기는 묶음을 어떻게 섞어야 가장 싼지 스스로 찾아야 합니다.

"손님이 고른 그대로, 가장 싼 값으로 계산하는 POS기를 만들자냥!"

상품은 k종류이고 0번부터 k-1번까지 번호가 붙어 있습니다. 아래 세 가지가 주어집니다.

  • price: price[i]는 i번 상품 1개의 낱개 가격입니다.
  • bundles: 묶음 상품 목록입니다. 묶음 하나는 길이 k+1인 리스트로, 앞의 k개 값은 그 묶음에 들어 있는 0번~k-1번 상품의 개수이고, 마지막 값은 묶음 가격입니다.
  • order: order[i]는 손님이 사려는 i번 상품의 개수입니다.

계산 규칙은 다음과 같습니다.

  • 낱개와 묶음을 섞어서 살 수 있고, 같은 묶음을 여러 번 사도 됩니다.
  • 산 상품의 개수가 주문과 정확히 같아야 합니다. 더 싸더라도 주문보다 많이 사게 되는 묶음은 쓸 수 없습니다.
  • 묶음 가격이 낱개로 사는 것보다 비쌀 수도 있습니다. 그런 묶음은 쓰지 않아도 됩니다.

주문을 정확히 맞추는 가장 적은 금액을 반환하는 solution 함수를 작성해 주세요.


제한 사항

  • data는 [price, bundles, order] 형태입니다.
  • 1 ≤ k(상품 종류 수, price와 order의 길이) ≤ 6
  • 1 ≤ price[i] ≤ 50,000
  • 1 ≤ 묶음 수 ≤ 15
  • 각 묶음의 상품 개수는 0 이상 6 이하이고, 한 묶음에 적어도 상품 1개는 들어 있습니다.
  • 1 ≤ 묶음 가격 ≤ 300,000
  • 0 ≤ order[i] ≤ 6
  • 모든 값은 정수입니다.

입출력 예

입력출력
[[6000, 4000, 8000], [[2, 0, 1, 15000], [1, 1, 0, 9000], [0, 2, 2, 22000]], [3, 2, 2]]36000
[[5000, 3000], [[3, 0, 13000], [1, 2, 10000]], [3, 4]]25000
[[2000, 3000, 1500], [[1, 1, 1, 7000], [2, 0, 0, 3500], [0, 3, 0, 6000]], [2, 2, 1]]11000

입출력 설명

입출력 예 #1

  • 0번 광어 6,000노드, 1번 우럭 4,000노드, 2번 갈치 8,000노드이고, 손님은 광어 3마리, 우럭 2마리, 갈치 2마리를 삽니다.
  • 모두 낱개로 사면 18,000 + 8,000 + 16,000 = 42,000노드입니다.
  • '광어 2 + 갈치 1' 묶음(15,000) + '광어 1 + 우럭 1' 묶음(9,000) + 우럭 1마리(4,000) + 갈치 1마리(8,000) = 36,000노드가 가장 쌉니다.
  • '우럭 2 + 갈치 2' 묶음(22,000)을 쓰면 남은 광어 3마리를 낱개로 사야 해서 40,000노드가 됩니다.

입출력 예 #2

  • 모두 낱개로 사면 15,000 + 12,000 = 27,000노드입니다.
  • '0번 1개 + 1번 2개' 묶음(10,000)을 두 번 사고 0번 상품 1개를 낱개(5,000)로 사면 25,000노드입니다.
  • '0번 3개' 묶음(13,000)과 1번 상품 4개 낱개(12,000)를 사도 25,000노드입니다. 25,000노드보다 싸게 살 수는 없습니다.

입출력 예 #3

  • 1번 상품 3개 묶음(6,000)은 싸지만 주문(2개)보다 많아서 쓸 수 없습니다.
  • 0·1·2번 상품 1개씩 묶음(7,000)은 낱개로 사는 것(6,500)보다 비쌉니다.
  • 0번 상품 2개 묶음(3,500) + 1번 상품 2개(6,000) + 2번 상품 1개(1,500) = 11,000노드가 가장 쌉니다.

예시 테스트

#입력기대값
1[[6000, 4000, 8000], [[2, 0, 1, 15000], [1, 1, 0, 9000], [0, 2, 2, 22000]], [3, 2, 2]]36000
2[[5000, 3000], [[3, 0, 13000], [1, 2, 10000]], [3, 4]]25000
3[[2000, 3000, 1500], [[1, 1, 1, 7000], [2, 0, 0, 3500], [0, 3, 0, 6000]], [2, 2, 1]]11000

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 13개도 함께 채점해요.