광물 캐기

프로그래머스

 

광물을 캘 곡괭이를 선택하면서 최소 피로도인 경우를 찾아 최소 피로도를 리턴하면 되는 문제.

 

백트래킹을 활용해서 풀었다.

---

풀이 코드

answer = int(1e9) # 최소 피로도

def backTracking(dia, iron, stone, minerals, result):
    global answer
    # print(dia, iron, stone, minerals, result)
    if dia == 0 and iron == 0 and stone == 0: # 더 사용할 곡괭이가 없다면 최솟값 갱신
        answer = min(answer, result)
        return
    if len(minerals) == 0: # 광산에 있는 모든 광물을 캤다면 최솟값 갱신
        answer = min(answer, result)
        return
    
    # 다이아 곡괭이가 있다면
    if dia > 0:
        cur_minerals = minerals[:5] # 현재 곡괭이로 캘 광석들
        cur_result  = 0 # 현재 곡괭이로 광석을 캐면 쌓이는 피로도
        for cm in cur_minerals:
            if cm == "diamond":
                cur_result += 1
            if cm == "iron":
                cur_result += 1
            if cm == "stone":
                cur_result += 1
        backTracking(dia - 1, iron, stone, minerals[5:], result + cur_result) # 백트래킹
    
    # 철 곡괭이가 있다면
    if iron > 0:
        cur_minerals = minerals[:5]
        cur_result  = 0
        for cm in cur_minerals:
            if cm == "diamond":
                cur_result += 5
            if cm == "iron":
                cur_result += 1
            if cm == "stone":
                cur_result += 1
        backTracking(dia, iron - 1, stone, minerals[5:], result + cur_result) # 백트래킹

    # 돌 곡괭이가 있다면
    if stone > 0:
        cur_minerals = minerals[:5]
        cur_result  = 0
        for cm in cur_minerals:
            if cm == "diamond":
                cur_result += 25
            if cm == "iron":
                cur_result += 5
            if cm == "stone":
                cur_result += 1
        backTracking(dia, iron, stone - 1, minerals[5:], result + cur_result) # 백트래킹
 

def solution(picks, minerals):
    global answer
    
    dia = picks[0] # 다이아 곡괭이 개수
    iron = picks[1] # 철 곡괭이 개수
    stone = picks[2] # 돌 곡괭이 개수
    
    
    backTracking(dia, iron, stone, minerals, 0) # 백트래킹 돌리기
    
    
    return answer

 

문제 보고 나서 바로 백트래킹 문제라는 생각이 들어서 로직 정리 후, 바로 구현해봤는데 이렇게 쉽게 풀릴지 몰랐다.

생각보다 실력이 잘 늘고 있을지도..?

그래도 절대 자만하지 말고 꾸준히 문제를 계속 풀자.