[프로그래머스] Lv2 - 광물 캐기

문제

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

프로그래머스

문제설명

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

입출력 예

picks	minerals	result
[1, 3, 2]	["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]	12
[0, 1, 1]	["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]	50

입출력 예 설명

입출력 예 #1

다이아몬드 곡괭이로 앞에 다섯 광물을 캐고 철 곡괭이로 남은 다이아몬드, 철, 돌을 1개씩 캐면 12(1 + 1 + 1 + 1+ 1 + 5 + 1 + 1)의 피로도로 캘 수 있으며 이때가 최소값입니다.

입출력 예 #2

철 곡괭이로 다이아몬드 5개를 캐고 돌 곡괭이고 철 5개를 캐면 50의 피로도로 캘 수 있으며, 이때가 최소값입니다.

 

1차시도

접근

다이아, 철, 돌 곡괭이의 순서로 

** 피로도 계산
다이아 25, 철 5, 돌1 로 치환하고
캘 때 광물/곡괭이
ex)
    다이아 곡괭이로 다이아 25/25 =1
    다이아 곡괭이로 철 5/25 
    철 곡괭이로 다이아 25/5 = 5
    돌 곡괭이로 다이아 25/1 = 25
    돌 곡괭이로 철 5/1 = 5

풀이

def solution(picks, minerals):
    answer = 0
    
    mineral_mapping = {
    "diamond": 25,
    "iron": 5,
    "stone": 1
    }
    # map(리스트 원소 각각을 인자로 실행될 함수, 리스트)
    # mineral_mapping[x] : x를 받아 mineral_mapping[x] 값을 반환, x = "diamond", "iron", "stone"
    new_minerals = list(map(lambda x: mineral_mapping[x], minerals)) 
    # ex [25, 25, 25, 5, 5, 25, 5, 1]
    if new_minerals == []:
        pass
    else:
    	# 다이아 곡괭이
        while picks[0] >0:
            i = 0
            while i<5:
                if new_minerals == []:
                    break
                else:
                    if new_minerals[0] / 25 >=1:
                        answer += int(new_minerals[0] / 25)
                    else:
                        answer += 1
                    i +=1
                    new_minerals.remove(new_minerals[0])
            picks[0]-=1
        # 철 곡괭이
        while picks[0] == 0 and picks[1] >0 :
            i = 0
            while i<5:
                if new_minerals == []:
                    break
                else:
                    if new_minerals[0] / 5 >=1:
                        answer += int(new_minerals[0] / 5)
                    else:
                        answer += 1
                    i +=1
                    new_minerals.remove(new_minerals[0])
            picks[1]-=1
        # 돌 곡괭이
        while picks[0] == 0 and picks[1] == 0 and picks[2] > 0:
            i = 0
            while i<5:
                if new_minerals == []:
                    break
                else:
                    if new_minerals[0] >=1:
                        answer += int(new_minerals[0])
                    else:
                        answer += 1
                    i +=1
                    new_minerals.remove(new_minerals[0])
            picks[1]-=1
    
    return answer

그리고 장렬하게 실패하고 말았다...

2차시도

접근

알고리즘에 대한 정석(?) 없이 야매로는 어려울 것 같아서, 완전탐색을 이용하기로 했다.

다만, 완전탐색 함수를 제대로 짜 본 적이 거의 없었기 때문에 이것저것 참고하고 공부하면서 풀었다.

 

 

풀이

total_fatigue=[[1,1,1],[5,1,1],[25,5,1]]
res=1000000000
mineral_mapping = {
    "diamond": 0,
    "iron": 1,
    "stone": 2
    }
 
# DFS 
def dfs(idx, dia, iron, stone, minerals, fatigue):

    if idx >= len(minerals) or (not dia and not iron and not stone):
        global res
        res = min(res, fatigue)
        return
 
    d_fatigue = 0
    i_fatigue = 0
    s_fatigue = 0
    # 광물 5개 캐기
    for i in range(idx, min(idx+5, len(minerals))):
        d_fatigue += total_fatigue[0][mineral_mapping[minerals[i]]]
        i_fatigue += total_fatigue[1][mineral_mapping[minerals[i]]]
        s_fatigue += total_fatigue[2][mineral_mapping[minerals[i]]]
 
    # 다이아 캘 때
    if dia:
        dfs(idx+5, dia-1, iron, stone, minerals, fatigue+d_fatigue)
 
    # 철 캘 때
    if iron:
        dfs(idx+5, dia, iron-1, stone, minerals, fatigue+i_fatigue)
 
    # 돌 캘 때
    if stone:
        dfs(idx+5, dia, iron, stone-1, minerals, fatigue+s_fatigue)
 

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