1def solution(picks, minerals):
2 bundles = []
3 tmp = [0, 0, 0]
4 DATA = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
5 answer = 0
6
7 for i in range(len(minerals)):
8 if minerals[i] == "diamond":
9 for j in range(3):
10 tmp[j] += DATA[j][0]
11 elif minerals[i] == "iron":
12 for j in range(3):
13 tmp[j] += DATA[j][1]
14 elif minerals[i] == "stone":
15 for j in range(3):
16 tmp[j] += DATA[j][2]
17
18 if (i+1) % 5 == 0 or i == len(minerals)-1:
19 bundles.append(tmp)
20 tmp = [0, 0, 0]
21 bundles = bundles[:sum(picks)]
22 bundles.sort(key= lambda x: -x[2])
23
24 for i in bundles:
25 for j in range(3):
26 if picks[j] != 0:
27 answer += i[j]
28 picks[j] -= 1
29 break
30
31 return answer
문제
- 3가지 종류의 곡괭이 개수와, 광물의 배열이 주어진다
- 광물을 캐는데 필요한 최소한의 피로도를 구하라
- 피로도 (순서대로 다이아몬드, 철, 돌을 캐는데 필요한 피로도이다)
다이아곡괭이 (1, 1, 1), 철곡괭이 (5, 1, 1), 돌곡괭이 (25, 5, 1)
- 규칙
- 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캔다
- 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용한다
- 광물은 주어진 순서대로만 캘 수 있다
- 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캔다.
- TC
- input
[1, 3, 2] [“diamond”, “diamond”, “diamond”, “iron”, “iron”, “diamond”, “iron”, “stone”]
- ouput
12
- input
해결방법
- 그리디로 푸는 문제이다
- 5개로 묶어서 곡괭이별 필요한 피로도를 계산하고, 피로도가 많이드는 순서대로 정렬하였다 (다이아 우선)
- 추가로 고려해야할 사항
만약, 곡괭이 개수가 3개라면 15개의 광물만 캘 수 있으므로 뒤의 광물은 버린다.