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

정답 코드 

def solution(picks, minerals):
    ans = []
    tired = [[1, 1, 1],
             [5, 1, 1],
             [25, 5, 1]]
    tools = {"diamond" : 1, "iron": 2, "stone": 3}
    
    def dfs(minerals, picks, tired_rate):
        # 종료 조건
        if sum(picks) == 0 or minerals == []:
            ans.append(tired_rate)
            return
        m = minerals[:5]
        # tool 을 picks에서 감소
        for t in range(3):
            if picks[t] > 0:
                picks[t] -= 1
                tired_rate_val = tired_rate_calculate(t, m)
                dfs(minerals[5:], picks, tired_rate+tired_rate_val)
                picks[t] += 1

    def tired_rate_calculate(t, minerals):
        tired_rate = 0
        for m in minerals:
            tired_rate += tired[t][tools[m]-1]

        return tired_rate
    dfs(minerals, picks, 0)
    ans.sort()
    return ans[0]

 

풀이

문제를 보고, 그리디와 dfs가 떠올랐습니다. 좀 더 익숙한 dfs로 문제를 풀었고, 모든 경우를 탐색하면서 피로도(tired_rate)를 계산하는 코드를 작성했습니다. 

1. dfs를 돌면서 사용할 수 있는 도구가 있다면, 도구를 사용하여 mineral[:5]만큼의 피로도를 계산합니다. 

2. 더 이상 사용할 수 있는 도구가 없거나, mineral이 고갈되면 종료합니다. 

 

제출하면 테스트 케이스가 절반만 맞는 문제가 있었는데, dfs안의 코드를 아래와 같이 작성했었습니다.

	# tool 을 picks에서 감소
        for t in range(3):
            if picks[t] > 0:
                picks[t] -= 1
                tired_rate_val += tired_rate_calculate(t, m)
                dfs(minerals[5:], picks, tired_rate)
                # tired_rate_val을 빼주는 로직이 추가되어야 함 !!
                picks[t] += 1

잘 보시면, picks는 -1을 해 준뒤 +1을 해줘서 다음 dfs에 지장이 없게 했지만 tired_rate는 더하는 로직만 있고 빼주는 로직이 없어서 값들이 계속 누적되는 오류가 있었습니다.

for t in range(3):
    if picks[t] > 0:
        picks[t] -= 1
        tired_rate_val = tired_rate_calculate(t, m)
        dfs(minerals[5:], picks, tired_rate+tired_rate_val)
        picks[t] += 1

위와 같이 코드를 += 가 아닌, 새로운 값에 할당하여 더하는 식으로 구현하니 잘 돌아가는 모습을 볼 수 있었습니다.