프로그래머스_광물캐기_level2(python)

※ 접근법

 문제를 봤을 때 어떤 곡괭이로 광물을 캐는지에 따라서 누적 피로도가 달라지니 바로 백트래킹인 것을 떠올렸다. 하지만 여기서 곡괭이가 최대 15개가 될 수 있는데 시간초과가 나지 않을까라는 생각이 들었다. 결국 여기서 시간초과가 발생했고 로직을 조금 수정했더니 문제가 해결됐다.

 

※ 풀이

 1. 곡괭이 종류만큼 반복을 해 곡괭이가 남아있다면 곡괭이로 광물을 캔다.

 2. 광물을 캐면서 누적 피로도를 계산해준다.

 3. 다음 재귀로 넘어갈 때 누적피로도, 다음 광물 인덱스, 쓴 곡괭이 개수를 계산해서 넘겨준다.

 

def dfs(picks,minerals,fatigue,m_idx,p_count,total):
    global count
    if m_idx >= len(minerals) or p_count == total: # 광물을 다 캤다면 곡괭이 다씀
        count = min(count,fatigue)        
        return
    for i in range(len(picks)): # 곡괭이 종류만큼 반복을 한다.
        if picks[i] > 0:
            temp = 0
            a_sum = 0
            picks[i] -= 1
            for j in range(m_idx,m_idx+5):
                temp = j
                if j == len(minerals):
                    break
                if i == 0:
                    a_sum += 1
                elif i == 1:
                    if minerals[j] == "diamond":
                        a_sum += 5
                        continue
                    a_sum += 1
                else:
                    if minerals[j] == "diamond":
                        a_sum += 25
                    elif minerals[j] == "iron":
                        a_sum += 5
                    else:
                        a_sum += 1
            dfs(picks,minerals,fatigue+a_sum,temp+1,p_count+1,total)
            picks[i] += 1
    
def solution(picks, minerals):
    global count
    count = 100000
    total = sum(picks)
    dfs(picks,minerals,0,0,0,total)
    return count

 

※ 회고

 처음에 시간초과가 발생할 것을 알면서도 쉽게 풀기 위해 코드를 구현했다. 역시나 시간초과가 발생했다.

앞으로는 쉽게 풀려고 하지말고 에러가 날 것 같으면 요행 부리지말고 열심히 코딩하자