bong-u/til

프로그래머스 - 광물 캐기 (L2)

수정일 : 2023-07-10

 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)

  • 규칙
    1. 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캔다
    2. 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용한다
    3. 광물은 주어진 순서대로만 캘 수 있다
    4. 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캔다.
  • TC
    • input

      [1, 3, 2] [“diamond”, “diamond”, “diamond”, “iron”, “iron”, “diamond”, “iron”, “stone”]

    • ouput

      12

해결방법

  • 그리디로 푸는 문제이다
  • 5개로 묶어서 곡괭이별 필요한 피로도를 계산하고, 피로도가 많이드는 순서대로 정렬하였다 (다이아 우선)
  • 추가로 고려해야할 사항

    만약, 곡괭이 개수가 3개라면 15개의 광물만 캘 수 있으므로 뒤의 광물은 버린다.