프로그래머스, 광물캐기

프로그래머스, 광물캐기

 

📜문제

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

프로그래머스

 

분류 : accepted

 

📜풀이

처음 문제를 봤을때, 무조건 곡괭이를 순서대로 다 써야하는 줄 알았다.

# [dia, iron, stone]
picks =  [0, 2, 1]

다이아몬드 곡괭이 없으니, 넘어가고 철 곡괭이로 10번 광물 캐기, 돌 곡괭이로 5번 광물 캐기

 

❌ 잘못된 풀이

from collections import deque

# [dia, iron, stone]
picks =  [0, 1, 99] 

minerals =  ["diamond", "diamond", "diamond", "diamond", "diamond", "diamond"]

# 피로도
degree_of_fatigue = [
    {'diamond' : 1, 'iron' : 1, 'stone': 1},
    {'diamond' : 5, 'iron' : 1, 'stone': 1},
    {'diamond' : 25, 'iron' : 5, 'stone': 1},
                     ]

queue = deque(minerals)

def total_fatigue():
    fatigue = 0 # 피로도 초기값
    for i in range(len(picks)):
        pick_cnt = picks[i] # 곡괭이 갯수

        for _ in range(5 * pick_cnt): # 해당 곡괭이로 광물 5개 캘 수 있음.
            if queue:
                mineral = queue.popleft() # target 광물
                fatigue += degree_of_fatigue[i][mineral]
            else:
                return fatigue

    return fatigue

result = total_fatigue()

print(result)

이 코드로 제출했을때 test case 2, 5,6,7, 11,12,13,14,15, 24, 25, 26, 27, 28, 29, 34, 35 불통!

너무 많은 불통에, 이건 로직자체가 이상하다.. 직감..ㅠ

[질문하기]로 이동해 다양한 반례를 넣어봤지만, 답이 나옴... ;;;;당황

 

🎈 그러다 발견한 글!

반례, 문제 잘못 이해.
사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
예를 들어, [3,3,3]의 곡괭이가 있다고 합시다.
그리고 처음에 다이아몬드 곡괭이를 고르고 5번 캤다고 합시다. 그러면 [2,3,3]의 상태가 될 것입니다.
그러면 다음 번 고를 수 있는 곡괭이는 무엇일까요? 위 상태에서는 모든 곡괭이가 가능합니다!!!
즉, 다이아몬드를 골랐다고 해서 끝까지 다이아몬드를 고를 필요는 없는 것입니다.
따라서 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다. 라는 규칙은, 5번 사용을 지키라는 규칙이지
곡괭이 종류에 관한 규칙은 아닙니다.

문제를 다시 보니,  최소한의 피로도로 광물을 캐려고 합니다. + 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

이 조건만 있을뿐... 문제를 내식대로 해석했다.

결국 여러 곡괭이를 사용해서 광물을 캐고 그중 피로도가 가장 작은 방식으로 캐면 되는 거였다!

완전탐색, dfs(재귀함수)로 풀면 되는 문제였다.

 

✅ 올바른 풀이

# [dia, iron, stone]
picks =  [0, 1, 1]

minerals = ["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]
# 피로도
degree_of_fatigue = [
    {'diamond' : 1, 'iron' : 1, 'stone': 1},
    {'diamond' : 5, 'iron' : 1, 'stone': 1},
    {'diamond' : 25, 'iron' : 5, 'stone': 1},
                     ]
total_f = []
def total_fatigue(idx, d_pick, i_pick, s_pick, f):
    if idx >= len(minerals) or (d_pick == i_pick == s_pick == 0):
        total_f.append(f) 
        return 
    
    d_f = 0
    i_f = 0
    s_f = 0
    for i in range(idx, min(idx + 5, len(minerals))):
        d_f += degree_of_fatigue[0][minerals[i]]
        i_f += degree_of_fatigue[1][minerals[i]]
        s_f += degree_of_fatigue[2][minerals[i]]

    if d_pick:
        total_fatigue(idx+5, d_pick-1, i_pick, s_pick, f+d_f)
    
    if i_pick:
        total_fatigue(idx+5, d_pick, i_pick-1, s_pick, f+i_f)
    
    if s_pick:
        total_fatigue(idx+5, d_pick, i_pick, s_pick-1, f+s_f)

total_fatigue(0, picks[0], picks[1], picks[2], 0)
print(total_f)
print(min(total_f))

 

📜 제출용 풀이

def solution(picks, minerals):
    degree_of_fatigue = [
        {'diamond' : 1, 'iron' : 1, 'stone': 1},
        {'diamond' : 5, 'iron' : 1, 'stone': 1},
        {'diamond' : 25, 'iron' : 5, 'stone': 1},
                     ]
    total_f = []
    def total_fatigue(idx, d_pick, i_pick, s_pick, f):
        if idx >= len(minerals) or (d_pick == i_pick == s_pick == 0):
            total_f.append(f) 
            return 

        d_f = 0
        i_f = 0
        s_f = 0
        for i in range(idx, min(idx + 5, len(minerals))):
            d_f += degree_of_fatigue[0][minerals[i]]
            i_f += degree_of_fatigue[1][minerals[i]]
            s_f += degree_of_fatigue[2][minerals[i]]

        if d_pick:
            total_fatigue(idx+5, d_pick-1, i_pick, s_pick, f+d_f)

        if i_pick:
            total_fatigue(idx+5, d_pick, i_pick-1, s_pick, f+i_f)

        if s_pick:
            total_fatigue(idx+5, d_pick, i_pick, s_pick-1, f+s_f)

    total_fatigue(0, picks[0], picks[1], picks[2], 0)

    return min(total_f)

 

😂 반성

문제의 의도를 잘 파악하고 분석하는 과정을 거치자!

그냥 바로 풀려고 하니, 이런 잘못된 접근을 하게 되는 것 같다.