프로그래머스 / 광물 캐기 / python

answer = 10e9

def cal(piro, c, i , minerals):
    result = 0
    j = i-5
    if i % 5 != 0:
        j = i - i%5
    if c == 0:
        for i in range(j, i):
            result += 1
    elif c == 1:
        for i in range(j, i):
            if minerals[i][0] == 'd':
                result += 5
            else:
                result += 1
    else:
        for i in range(j, i):
            if minerals[i][0] == 'd':
                result += 25
            elif minerals[i][0] == 'i':
                result += 5
            else:
                result += 1
    return result
def dfs(idx,minerals, d_g, i_g, s_g, piro):
    global answer
    if idx >= len(minerals) or d_g + i_g + s_g == 0:
        answer = min(answer, piro)
        return

    i = idx + 5
    if idx + 5 > len(minerals):
        i = len(minerals)
        
    if d_g:
        dfs(i, minerals, d_g-1, i_g, s_g, piro + cal(piro, 0, i, minerals))
    if i_g:
        dfs(i, minerals, d_g, i_g-1, s_g, piro + cal(piro, 1, i, minerals))
    if s_g:
        dfs(i, minerals, d_g, i_g, s_g-1, piro + cal(piro, 2, i, minerals))
    

def solution(picks, minerals):
    global answer
    
    dfs(0,minerals, picks[0], picks[1], picks[2], 0)
    return answer

백트래킹으로 푼 문제

각 곡갱이에 대해서 곡갱이가 존재한다면 dfs 진행하는 방식으로 해결
더 이상 남은 곡갱이가 없거나 mineral을 끝까지 다 캔 상태라면 dfs 종료

종료시 최소 값을 저장해 나가면서 답을 구할 수 있다.