[Programmers] - Python / 파이썬 - 광물 캐기

문제

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

시간 복잡도

• dfs를 돌며 3번씩 k번 반복 -> $O(3^k)$
• k의 최댓값은 15이기 때문에 시간은 충분하다.
• 3^15 = 14,348,907

문제 접근법

1. 광물을 5개 단위로 배열에 담아 2차원 배열로 만든다.
2. 백트래킹을 통해 모든 경우의 수를 계산한다.
   2-1. 모든 광물을 캤거나 곡괭이를 다 쓴 경우, 최솟값을 비교하여 변경한다.
   2-2. 현재 캐야 할 광물들을 캘 때 필요한 피로도를 각 곡괭이마다 계산한다.
   2-3. 2-2에서 계산한 피로도를 더한 후, 사용한 곡괭이의 수를 줄이고 캐야 할 광물의 인덱스를 늘려 백트래킹을 계속 한다.

코드

# Programmers
# Lv.2 - 광물 캐기

d = {'diamond': [1, 5, 25], 'iron': [1, 1, 5], 'stone': [1, 1, 1]}
ans = 15 * 25 * 50

def calculate(pick, minerals):
    cnt = 0
    for mineral in minerals:
        cnt += d[mineral][pick]
    return cnt

def dfs(i, dia, iron, stone, minerals, total):
    if i == len(minerals) or (dia + iron + stone) == 0:
        global ans
        ans = min(ans, total)
        return
    
    if dia:
        dfs(i + 1, dia - 1, iron, stone, minerals, total + calculate(0, minerals[i]))
    if iron:
        dfs(i + 1, dia, iron - 1, stone, minerals, total + calculate(1, minerals[i]))
    if stone:
        dfs(i + 1, dia, iron, stone - 1, minerals, total + calculate(2, minerals[i]))
        
def solution(picks, minerals):
    minerals_sep = [minerals[i: i + 5] for i in range(0, len(minerals), 5)]
    dfs(0, picks[0], picks[1], picks[2], minerals_sep, 0)
    
    return ans