99클럽 TIL (240829)

> [Middler] 광물 캐기

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

 

🔥다시보기🔥

 

 

문제 풀이 과정

처음에 문제를 잘못읽어서 곡괭이를 순차적으로 골랐는데, 그게 아니었다. 그래서 모든 곡괭이에서 광물을 캐는 DFS를 생각했다. 

아쉽게도 DFS로도 문제를 해결하지 못했다.

 

💩 틀린 문제 풀이

큐에 넣고 현재 곡괭이에서 미네랄을 캔 모든 경우를 answer에 담는 로직을 구현하려고 했다... 하지만 시간도 너무 지체되고 문제가 풀리지 않았다.

def addTired(pick, mineral, num) :
    if pick == 0 :
        num[pick] += 1
    elif pick == 1 :
        if mineral == "diamond" :
            num[pick] += 5
        else :
            num[pick] += 1
    else :
        if mineral == "diamond" :
            num[pick] += 25
        elif mineral == "iron" :
            num[pick] += 5
        else : 
            num[pick] += 1

def solution(picks, minerals):
    answer = [0] * len(picks)
    
    q = []
    for i in range(len(picks)) :
        if picks[i] != 0 :
            v = [False] * len(minerals)
            q.append((i, picks[i] * 5, v))
    
            while q :
                pick, pCnt, v = q.pop()
                
                if pCnt == 0 :
                    continue
                print(pick,pCnt,v, answer)
                for j, m in enumerate(minerals) :
                    if not v[j] and pCnt > 0 :
                        pCnt -= 1
                        addTired(pick, m, answer)
                        v[j] = True

                        if pick == len(picks)-1 :
                            q.append((0, pCnt, v))
                        else :
                            q.append((pick+1, pCnt, v))
            
    return min(answer)

 

문제 풀이

DFS 풀이

• 참조 : https://toki0411.tistory.com/80
• ✨ 기억할것!
  • 조건문으로 바로 구현하기보다 그래프로 생각해보기! (광물 피로도 표)
  • 재귀, 반복의 경우 base condition을 통해 재귀를 탈출시켜야 한다. 조건을 잘 기입하자!

def solution(picks, minerals):
    answer = []
    tired = [[1,1,1],[5,1,1],[25,5,1]]
    mineralCol = {"diamond" : 0, "iron" : 1, "stone" : 2}
        
    def dfs(picks, minerals, value) :
        # 곡괭이를 다쓰면 리턴
        if sum(picks) == 0 or len(minerals) == 0:
            answer.append(value)
            return
        
        m = minerals[:5]
        
        for i in range(3) :
            if picks[i] > 0 :
                picks[i] -= 1
                pVal = 0
                for j in m :
                    pVal += tired[i][mineralCol[j]]
                dfs(picks, minerals[5:], value+pVal)
                picks[i] += 1
                
    dfs(picks, minerals, 0)
    return min(answer)

 

그리디

• 참조 : 블로그 (ㅠ글이해하기)
• 그리디 알고리즘으로 푸는 게 더 효과적이다. 5개씩 다이아몬드, 철, 곡괭이를 사용했을 때 피로도를 계산해 놓으면 돌 곡괭이를 사용했을 때를 기준으로 내림차순 정렬하면 최선의 경우의 수를 찾을 수 있다.
• 이렇게 해결할 수 있는 이유는 돌, 철, 다이아몬드를 비교했을 때 효율이 차이나기 때문이다. 무조건 철 곡괭이가 돌보다 효율이 높고, 다이아몬드가 곡괭이가 철보다 효율이 높다. 따라서 전부 탐색할 필요없이 다이아몬드, 철, 돌 순대로 나열하고 다이아몬드, 철, 돌 곡괭이가 있는 대로 적용하면 된다.

 

회고 및 느낀점

그리디 문제는 여전히 어렵다...😢