프로그래머스 광물 캐기 Python

프로그래머스 문제 (Python) — 광물 캐기

문제

마인은 다이아몬드, 철, 돌 곡괭이를 가지고 광산에서 광물을 캐려고 합니다.

• 곡괭이는 종류별로 0개 이상 5개 이하를 가질 수 있습니다.
• 한 곡괭이는 최대 5번만 사용할 수 있고, 이후에는 사용할 수 없습니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 각 곡괭이로 광물을 캘 때의 피로도는 다음과 같습니다.

곡괭이 \ 광물	다이아몬드	철	돌
다이아 곡괭이	1	1	1
철 곡괭이	5	1	1
돌 곡괭이	25	5	1

• 목표는 주어진 곡괭이와 광물 순서를 바탕으로 최소 피로도를 계산하는 것입니다.

---

테스트케이스

1.

• 입력: picks = [1, 3, 2], minerals = ["diamond","diamond","diamond","iron","iron","diamond","iron","stone"]
• 출력: 12

2.

• 입력: picks = [0, 1, 1], minerals = ["diamond","diamond","diamond","diamond","diamond","iron","iron","iron","iron","iron","diamond"]
• 출력: 50

---

문제 작동원리

1. 곡괭이 수에 따라 최대 캘 수 있는 광물 수는 (sum(picks) × 5)개입니다.
   즉, 광물 배열이 아무리 길어도 실제로는 이 범위까지만 고려합니다.
2. 광물을 5개 단위로 끊어 블록을 만듭니다. (마지막 블록은 5개 미만 가능)
3. 각 블록을 “돌 곡괭이 기준 피로도”로 환산하여 난이도를 측정합니다.
   
   • 예: 다이아 5개 블록은 돌 곡괭이 기준으로 \(25 \times 5 = 125\) 점수.
4. 난이도 점수가 높은 블록부터 좋은 곡괭이를 배정합니다.
   
   • 다이아 곡괭이 → 철 곡괭이 → 돌 곡괭이 순서.
5. 실제 배정된 곡괭이로 블록 피로도를 다시 계산해 합산합니다.

이 과정을 통해 최소 피로도가 계산됩니다.

---

아이디어

• 탐욕법(Greedy) 사용
  • 돌 곡괭이로 캤을 때 가장 피로도가 높은 구간은 다이아가 많이 포함된 블록입니다.
  • 따라서 가장 좋은 곡괭이를 이런 블록에 먼저 배정하면 전체 피로도를 최소화할 수 있습니다.
• 핵심: 블록을 전부 고려하지 않고, \(5 \times \text{sum(picks)}\)까지만 고려해야 합니다.
  • 이 부분을 빠뜨리면 뒤쪽 블록에 좋은 곡괭이가 배정되는 오류가 발생합니다.

---

코드

def check(minerals: list, start: int, sorting: int) -> [int, int]:
    N = len(minerals)
    cnt = 0
    for i in range(start, start+5):
        if i >= N:
            break
        if sorting == 0:  # 다이아 곡괭이
            cnt += 1
        elif sorting == 1:  # 철 곡괭이
            if minerals[i] == 'diamond':
                cnt += 5
            else:  # iron, stone
                cnt += 1
        elif sorting == 2:  # 돌 곡괭이
            if minerals[i] == 'diamond':
                cnt += 25
            elif minerals[i] == 'iron':
                cnt += 5
            else:  # stone
                cnt += 1
    return [cnt, start]

def solution(picks, minerals):
    answer = 0
    easy = []

    # 사용할 수 있는 곡괭이로 캘 수 있는 범위까지만 블록화
    limit = min(len(minerals), (picks[0] + picks[1] + picks[2]) * 5)
    for start in range(0, limit, 5):
        easy.append(check(minerals, start, 2))  # 돌 곡괭이 기준 점수
    
    # 돌 기준 점수가 큰 블록부터 정렬
    easy.sort(reverse=True, key=lambda x: x[0])
    N = len(easy)
    i = 0
    cnt = 0
    
    # 다이아 곡괭이부터 배정
    while i < N and picks[0] > 0:
        cnt += check(minerals, easy[i][1], 0)[0]
        i += 1
        picks[0] -= 1
    
    # 철 곡괭이 배정
    while i < N and picks[1] > 0:
        cnt += check(minerals, easy[i][1], 1)[0]
        i += 1
        picks[1] -= 1
    
    # 돌 곡괭이 배정
    while i < N and picks[2] > 0:
        cnt += check(minerals, easy[i][1], 2)[0]
        i += 1
        picks[2] -= 1
    
    answer = cnt
    return answer
    

---

결론

이 문제는 탐욕적 선택이 정답이 되는 대표적인 문제입니다.

• 광물을 5개 단위로 묶고,
• 돌 곡괭이 기준 피로도를 점수화하여 정렬한 뒤,
• 가장 좋은 곡괭이를 점수가 큰 블록부터 배정하면,
• 전체 피로도가 최소화됩니다.

핵심 포인트는 “실제로 캘 수 있는 범위까지만 고려한다”는 제약을 지켜야 한다는 점입니다.
이 한 줄을 지키면 모든 테스트케이스를 통과할 수 있습니다.