[Python] 프로그래머스: 광물 캐기

 

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

해결 방법

이 문제의 경우 DFS, BFS로 풀 수도 있지만, 그리디 알고리즘으로 푸는 것이 최선이라고 생각합니다.

먼저 5개가 한 단위가 되기 때문에, 5개씩 끊고 다이아몬드, 철, 돌 곡갱이를 사용했을 때 피로도를 계산해놓으면 돌 곡갱이를 사용했을 때를 기준으로 내림차순 정렬하면 최선의 경우의 수를 찾을 수 있습니다.

이렇게 해결할 수 있는 이유는 돌, 철, 다이아몬드를 비교했을 때 효율이 차이나기 때문입니다.

무조건 철 곡갱이가 돌보다 효율이 높고, 다이아몬드 곡갱이가 철 곡갱이보다 효율이 높습니다.

따라서 전부 탐색할 필요 없이 다이아몬드, 철, 돌이 많은 순서대로 나열하고 다이아몬드, 철, 돌 곡갱이가 있는 대로 적용하면 됩니다.

다이아몬드, 철, 돌이 많은 순서는 돌 곡갱이로 캤을 때 기준으로 피로도를 내림차순하면 됩니다.

코드

def solution(picks, minerals):
    # 광물들 5개씩 끊기
    minerals_divided = list_divided(minerals, 5)

    # 곡갱이 종류별로 사용했을 때 피로도 계산
    costs = []  # 피로도 종합
    for section in minerals_divided:
        cost = [0, 0, 0]  # 다이아몬드, 철, 돌 곡갱이를 사용했을 때 피로도
        for mineral in section:
            if mineral == "diamond":  # 다이아몬드 광석을 캘 경우
                cost[0] += 1
                cost[1] += 5
                cost[2] += 25
            elif mineral == "iron":  # 철 광석을 캘 경우
                cost[0] += 1
                cost[1] += 1
                cost[2] += 5
            else:  # 돌을 캘 경우
                cost[0] += 1
                cost[1] += 1
                cost[2] += 1
        costs.append(cost)
    else:
        while len(costs) > sum(picks):  # 곡갱이 숫자보다 더 많은 광물을 캘 수 없음
            costs.pop()
    # 피로도 최소값 계산
    costs_sorted = sorted(costs, key=lambda x: x[2], reverse=True)
    cost_integrated = 0
    for cost in costs_sorted:
        if picks[0] > 0:
            cost_integrated += cost[0]
            picks[0] -= 1
            continue

        if picks[1] > 0:
            cost_integrated += cost[1]
            picks[1] -= 1
            continue

        if picks[2] > 0:
            cost_integrated += cost[2]
            picks[2] -= 1

    return cost_integrated


def list_divided(target_list: list, n: int):
    return [target_list[i:i+n] for i in range(0, len(target_list), n)]