[프로그래머스][그리디][백트래킹] 광물 캐기

광물 캐기

프로그래머스

 

 

내 풀이

• 곡괭이수가 더 많은 경우와 곡괭이가 부족한 경우로 나누어 계산
  • → 그냥 광물을 캘수있을만큼만 잘라서 곡괭이가 넉넉한 경우만 확인했으면 됨
• 곡괭이 수가 많은 경우
• 5개씩 묶은 뒤에 (다이아, 철, 돌) 순으로 많은 묶음 부터 단단한 곡괭이로 처리하면 됨 (그리디)
• 곡괭이가 부족한 경우
  • 가능한 곡괭이 리스트를 만들고, 중복 순열을 set 해서 최소 피로도를 가지는 방법으로 업데이트
• 📍주의할 점
  • Counter가 정렬되어 나오지 않기 때문에 정렬을 해줘야함
• key=lambda x:[(x[i][0],-x[i][1]) for i in range(len(x))]
  • 튜플 각각을 모두 보면서 정렬하고 싶으면 람다식에 for문 넣어서 돌리면됨

# 원래코드
from itertools import permutations
from collections import defaultdict, Counter

def solution(picks, minerals):
    answer = 0
    n=len(minerals)
    m=sum(picks)
    
    pick=['diamond', 'iron', 'stone']
    picks_dict=defaultdict(int)
    picks_total=[]
    for idx,cnt in enumerate(picks):
        picks_dict[pick[idx]]=idx
        picks_total+=[idx]*cnt
    
    minerals_cnt=[]
    
    for i in range(n):
        minerals[i]=pick.index(minerals[i])
    
    for i in range(0,n,5):
        cnt_lst=list(Counter(minerals[i:i+5]).items())
        cnt_lst.sort()
        minerals_cnt.append(cnt_lst)
    
    if m>=(n-1)//5+1: # 곡괭이 수가 더 많은 경우
        minerals_cnt.sort(key=lambda x:[(x[i][0],-x[i][1]) for i in range(len(x))])
    
        for mineral in minerals_cnt:
            p=-1
            for idx,pick in enumerate(picks):
                if pick:
                    p=idx
                    picks[idx]-=1
                    break
            if p==-1:
                break

            for mn in mineral:
                if p-mn[0]<=0:
                    answer+=1*mn[1]
                else:
                    answer+=(5**(p-mn[0]))*mn[1]
            
    else: #곡괭이가 부족한 경우
        answer=100000000
        for perm in set(permutations(picks_total,m)):
            tmp=0
            for idx,mineral in enumerate(minerals_cnt):
                if idx>=len(perm):
                    break

                for mn in mineral:
                    if perm[idx]-mn[0]<=0:
                        tmp+=1*mn[1]
                    else:
                        tmp+=(5**(perm[idx]-mn[0]))*mn[1]
            answer=min(answer,tmp)

    return answer

• 곡괭이 수에 맞게 자르면 훨씬 간단한 코드가 됨

# 5번 캐고나면 끝
from itertools import permutations
from collections import defaultdict, Counter

def solution(picks, minerals):
    answer = 0
    m=sum(picks)
    minerals=minerals[:5*m]
    n=len(minerals)
    
    pick=['diamond', 'iron', 'stone']
    picks_dict=defaultdict(int)
    picks_total=[]
    for idx,cnt in enumerate(picks):
        picks_dict[pick[idx]]=idx
        picks_total+=[idx]*cnt
    
    minerals_cnt=[]
    
    for i in range(n):
        minerals[i]=pick.index(minerals[i])
    
    for i in range(0,n,5):
        cnt_lst=list(Counter(minerals[i:i+5]).items())
        cnt_lst.sort()
        minerals_cnt.append(cnt_lst)
    
    minerals_cnt.sort(key=lambda x:[(x[i][0],-x[i][1]) for i in range(len(x))])
    
    for mineral in minerals_cnt:
        p=-1
        for idx,pick in enumerate(picks):
            if pick:
                p=idx
                picks[idx]-=1
                break
        if p==-1:
            break

        for mn in mineral:
            if p-mn[0]<=0:
                answer+=1*mn[1]
            else:
                answer+=(5**(p-mn[0]))*mn[1]
    
    return answer

 

 

---

다른 사람 풀이

• 백트래킹

def solution(picks, minerals):
    fatigue_table = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    mineral_index = {'diamond': 0, 'iron': 1, 'stone': 2}
    minerals=[mineral_index[x] for x in minerals]

    n = len(minerals)
    max_rounds = (n + 4) // 5

    answer = float('inf')

    def dfs(current_picks, round_num, fatigue):
        nonlocal answer

        # 종료 조건: 라운드 초과 또는 곡괭이 소진
        if round_num == max_rounds or sum(current_picks) == 0:
            answer = min(answer, fatigue)
            return

        for pick in range(3):
            if current_picks[pick] == 0:
                continue

            current_picks[pick] -= 1

            tmp = 0
            start = round_num * 5
            end = min(start + 5, n)

            for mineral in minerals[start:end]:
                tmp += fatigue_table[pick][mineral]

            dfs(current_picks, round_num + 1, fatigue + tmp)
            current_picks[pick] += 1  # 백트래킹 복원

    dfs(picks[:], 0, 0)
    return answer