[level 2] 힌트 스테이지 - 468377

문제 링크

성능 요약

메모리: 11.4 MB, 시간: 35.83 ms

구분

코딩테스트 연습 > 2025 카카오 하반기 2차

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2026년 08월 24일 11:47:00

문제 설명

당신은 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 ≤ 16
- cost[i]의 길이 = n
- cost[i][j]는 i+1번 스테이지에서 힌트권을 j개 사용했을 때의 해결 비용입니다.
  - 1 ≤ cost[i][j] ≤ 100,000
  - cost[i][j] > cost[i][j+1]
hint의 길이 = n-1
- 2 ≤ hint[i]의 길이 = k+1 ≤ 20
- hint[i][0]은 i+1번 스테이지에서 판매하는 힌트 번들의 판매 가격입니다.
  - 0 ≤ hint[i][0] ≤ 1,000,000
- hint[i][j](j>0)는 i+1번 스테이지에서 판매하는 힌트 번들에 j번째로 들어있는 힌트권 번호입니다.
  - i+1 < hint[i][j] ≤ n (j>0)

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

그룹	총점	추가 제한 사항
#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 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges