문제 설명
당신은 n개의 스테이지(1번 → n번)를 순서대로 모두 해결해야 합니다. 각 스테이지를 클리어 하기 위해서는 해결 비용이 들며, 힌트권을 많이 사용할수록 비용이 줄어듭니다.
- 힌트권에는 1~
n번까지의 번호가 붙어 있습니다. i번 힌트권은 오직i번 스테이지에서만 사용 가능합니다.- 하나의 스테이지에서 사용할 수 있는 힌트권의 최대 개수는
n-1개입니다. - 초기에는 힌트권을 가지고 있지 않습니다.
마지막 스테이지를 제외한 각 스테이지에서는 해당 스테이지에서 판매하는 힌트 번들을 최대 1개 구매할 수 있습니다. 힌트 번들은 이후 스테이지의 힌트권을 제공하며 비용을 주고 사야합니다.
- 스테이지마다 구매 가능한 힌트 번들의 종류와 판매 가격이 다를 수 있습니다.
- 힌트 번들에는 힌트권이 총
k장 들어 있으며, 같은 번호의 힌트권이 여러 장 포함될 수도 있습니다. i번 스테이지에서 판매하는 힌트 번들에는 항상i+1번 이상의 번호를 가진 힌트권만 들어 있습니다.
당신은 모든 스테이지를 해결하는데 필요한 최소 비용을 구해야 합니다.
예를 들어 각 스테이지의 해결 비용과 힌트 번들 정보가 아래 표와 같다고 가정해 보겠습니다.
스테이지 해결 비용(힌트권 사용 수에 따른 해결 비용)
| 스테이지\힌트권 사용 수 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 스테이지 #1 | 160 | 140 | 120 | 110 | 60 |
| 스테이지 #2 | 290 | 270 | 260 | 120 | 10 |
| 스테이지 #3 | 160 | 130 | 120 | 60 | 20 |
| 스테이지 #4 | 160 | 120 | 80 | 70 | 20 |
| 스테이지 #5 | 110 | 70 | 60 | 30 | 20 |
힌트 번들
| 스테이지 | 판매 가격 | 힌트권 번호 |
|---|---|---|
| 스테이지 #1 | 40 | #2, #3 |
| 스테이지 #2 | 40 | #5, #3 |
| 스테이지 #3 | 20 | #5, #4 |
| 스테이지 #4 | 50 | #5, #5 |
다음과 같이 총 810(= 160+40+270+130+20+120+70)만큼의 비용으로 모든 스테이지를 해결 가능하며, 이보다 적은 비용은 불가능합니다.
- 스테이지 #1을 힌트권을 사용하지 않고 160만큼의 비용으로 해결합니다. 비용을 40만큼 지불하고 #2, #3 힌트권을 얻습니다.
- 스테이지 #2을 힌트권 1장을 사용하고 270만큼의 비용으로 해결합니다.
- 스테이지 #3을 힌트권 1장을 사용하고 130만큼의 비용으로 해결합니다. 비용을 20만큼 지불하고 #5, #4 힌트권을 얻습니다.
- 스테이지 #4를 힌트권 1장을 사용하고 120만큼의 비용으로 해결합니다.
- 스테이지 #5를 힌트권 1장을 사용하고 70만큼의 비용으로 해결합니다.
각 스테이지의 힌트권 사용 수에 따른 해결 비용을 담은 2차원 정수 배열 cost와 각 스테이지에서 구매 가능한 힌트 번들의 비용과 포함된 힌트권 번호를 담은 2차원 정수 배열 hint가 매개변수로 주어집니다. 모든 스테이지를 해결하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 2 ≤
cost의 길이 =n≤ 16cost[i]의 길이 =ncost[i][j]는i+1번 스테이지에서 힌트권을j개 사용했을 때의 해결 비용입니다.- 1 ≤
cost[i][j]≤ 100,000 cost[i][j]>cost[i][j+1]
- 1 ≤
hint의 길이 =n-1- 2 ≤
hint[i]의 길이 =k+1≤ 20 hint[i][0]은i+1번 스테이지에서 판매하는 힌트 번들의 판매 가격입니다.- 0 ≤
hint[i][0]≤ 1,000,000
- 0 ≤
hint[i][j](j>0)는i+1번 스테이지에서 판매하는 힌트 번들에j번째로 들어있는 힌트권 번호입니다.i+1<hint[i][j]≤n(j>0)
- 2 ≤
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 30% | k = 1 |
| #2 | 20% | hint[i][0] = 0 |
| #3 | 50% | 추가 제한 사항 없음 |
입출력 예
| cost | hint | result |
|---|---|---|
| [[160, 140, 120, 110, 60], [290, 270, 260, 120, 10], [160, 130, 120, 60, 20], [160, 120, 80, 70, 20], [110, 70, 60, 30, 20]] | [[40, 2, 3], [40, 5, 3], [20, 5, 4], [50, 5, 5]] | 810 |
| [[110, 100, 90, 80, 70, 50, 10], [170, 160, 150, 140, 130, 110, 30], [260, 250, 190, 180, 170, 130, 100], [170, 150, 120, 90, 60, 40, 30], [220, 140, 110, 100, 70, 60, 50], [290, 180, 150, 130, 100, 20, 10], [110, 100, 90, 70, 50, 40, 30]] | [[40, 3, 4, 3], [80, 3, 7, 4], [40, 7, 6, 5], [40, 7, 5, 5], [50, 6, 7, 6], [30, 7, 7, 7]] | 1080 |
| [[290, 270, 170, 100, 60, 20], [210, 190, 180, 170, 120, 80], [200, 180, 170, 80, 40, 20], [100, 90, 70, 60, 40, 10], [230, 200, 170, 150, 90, 80], [150, 100, 80, 60, 40, 10]] | [[230, 2, 2, 2, 2], [330, 5, 3, 4, 3], [180, 5, 4, 4, 6], [280, 5, 5, 6, 6], [260, 6, 6, 6, 6]] | 1180 |
| [[49250, 42271, 40724, 36310, 32560, 30670, 24100, 10378], [58510, 56101, 54078, 32864, 31443, 19451, 18098, 7187], [68812, 66112, 65024, 60529, 53992, 39865, 31325, 17700], [13768, 12866, 11379, 10425, 6853, 6176, 5655, 2556], [51748, 48647, 41478, 39756, 25302, 18081, 16504, 811], [52690, 34113, 32370, 29555, 19343, 11763, 7566, 5962], [9306, 9190, 8196, 7573, 6275, 4723, 1316, 212], [40713, 40158, 31449, 22349, 20956, 20377, 19489, 14450]] | [[0, 2, 4, 6, 2], [0, 6, 3, 3, 4], [0, 6, 4, 5, 5], [0, 7, 5, 8, 7], [0, 7, 7, 7, 7], [0, 7, 7, 7, 8], [0, 8, 8, 8, 8]] | 267789 |
| [[330, 300, 277, 162, 126], [640, 392, 358, 345, 231], [960, 872, 678, 392, 113], [210, 195, 176, 42, 37], [980, 964, 623, 327, 154]] | [[976, 2, 2, 3, 5, 3, 3], [746, 3, 3, 3, 3, 4, 3], [319, 5, 4, 4, 4, 4, 4], [966, 5, 5, 5, 5, 5, 5]] | 3004 |
| [[230, 223, 192, 93, 59, 33], [290, 240, 193, 117, 113, 42], [950, 908, 796, 598, 574, 328], [720, 692, 588, 237, 102, 61], [780, 569, 522, 450, 337, 293], [850, 837, 768, 568, 382, 124]] | [[158, 2, 2, 3], [260, 5, 4, 3], [268, 4, 4, 4], [426, 5, 5, 6], [330, 6, 6, 6]] | 3426 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
스테이지 해결 비용
| 스테이지\힌트권 사용 수 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 스테이지 #1 | 110 | 100 | 90 | 80 | 70 | 50 | 10 |
| 스테이지 #2 | 170 | 160 | 150 | 140 | 130 | 110 | 30 |
| 스테이지 #3 | 260 | 250 | 190 | 180 | 170 | 130 | 100 |
| 스테이지 #4 | 170 | 150 | 120 | 90 | 60 | 40 | 30 |
| 스테이지 #5 | 220 | 140 | 110 | 100 | 70 | 60 | 50 |
| 스테이지 #6 | 290 | 180 | 150 | 130 | 100 | 20 | 10 |
| 스테이지 #7 | 110 | 100 | 90 | 70 | 50 | 40 | 30 |
힌트 번들
| 스테이지 | 판매 가격 | 힌트권 번호 |
|---|---|---|
| 스테이지 #1 | 40 | #3, #4, #3 |
| 스테이지 #2 | 80 | #3, #7, #4 |
| 스테이지 #3 | 40 | #7, #6, #5 |
| 스테이지 #4 | 40 | #7, #5, #5 |
| 스테이지 #5 | 50 | #6, #7, #6 |
| 스테이지 #6 | 30 | #7, #7, #7 |
다음과 같이 총 1080(= 110+40+170+190+150+40+110+50+150+30+40)만큼의 비용으로 모든 스테이지를 해결 가능하며, 이보다 적은 비용은 불가능합니다.
- 스테이지 #1을 힌트권을 사용하지 않고 110만큼의 비용으로 해결합니다. 힌트 번들을 구매합니다. 비용을 40만큼 지불하고 #3, #4, #3 힌트권을 얻습니다.
- 스테이지 #2을 힌트권을 사용하지 않고 170만큼의 비용으로 해결합니다.
- 스테이지 #3을 힌트권을 2장 사용하고 190만큼의 비용으로 해결합니다.
- 스테이지 #4를 힌트권을 1장 사용하고 150만큼의 비용으로 해결합니다. 힌트 번들을 구매합니다. 비용을 40만큼 지불하고 #7, #5, #5 힌트권을 얻습니다.
- 스테이지 #5를 힌트권을 2장 사용하고 110만큼의 비용으로 해결합니다. 힌트 번들을 구매합니다. 비용을 50만큼 지불하고 #6, #7, #6 힌트권을 얻습니다.
- 스테이지 #6을 힌트권을 2장 사용하고 150만큼의 비용으로 해결합니다. 힌트 번들을 구매합니다. 비용을 30만큼 지불하고 #7, #7, #7 힌트권을 얻습니다.
- 스테이지 #7을 힌트권을 5장 사용하고 40만큼의 비용으로 해결합니다.
따라서 1080을 return 합니다.
입출력 예 #3
힌트 번들을 한 번도 구매하지 않으면 최소 비용으로 모든 스테이지를 해결 가능합니다. 따라서 1180을 return 합니다.
입출력 예 #4
힌트 번들을 모두 구매하면서 스테이지마다 힌트권을 사용 가능한 최대 개수만큼 사용하면 최소 비용으로 모든 스테이지를 해결 가능합니다. 따라서 267789를 return 합니다.
입출력 예 #5
3004를 return 해야 합니다.
입출력 예 #6
3426을 return 해야 합니다.