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

광물 캐기

프로그래머스

 

 

• 첫 풀이- fail
  • 그냥 무조건 다이아몬드-철-돌 순으로 사용했는데
  • 다이아몬드를 뒤에 사용하는 것이 더 최소가 될 가능성이 있음

def solution(picks, minerals):
    answer = 0
    picks_name=["diamond", "iron", "stone"]
    start=0
    for idx, pick in enumerate(picks):
        for i in range(start, start+(5*pick)):
            if i>=len(minerals):
                break
            if picks_name.index(minerals[i]) >=idx:
                answer+=1
            elif picks_name.index(minerals[i]) ==idx-1:
                answer+=5
            else:
                answer+=25
        start+=5*pick
                
    return answer

 

 

• 두번째 풀이 - fail (시간초과)
  • 백트래킹 
  • 5개씩 했을 때 필요한 수만큼 다 뽑거나, 그 수보다 곡괭이 개수가 적어서 곡괭이를 모두 사용했을 때

answer = int(1e9)
def solution(picks, minerals):
    picks_all=[]
    for idx, pick in enumerate(picks):
        for i in range(pick):
            picks_all.append(idx)
            
    picks_name=["diamond", "iron", "stone"]
    clst=[]
    
    def comb(start, cnt):
        global answer 
        if cnt==len(minerals)//5+1 or (cnt==sum(picks) and cnt<len(minerals)//5+1):
            start=0
            tmp=0
            for c in clst:
                for idx in range(start, start+5):
                    if idx>= len(minerals):
                        break
                        
                    if picks_name.index(minerals[idx])>= c:
                        tmp+=1
                    elif picks_name.index(minerals[idx])== c-1:
                        tmp+=5
                    else:
                        tmp+=25
                start+=5
            
            answer=min(answer, tmp)
            return
        
        for i in range(len(picks_all)):
            if clst.count(picks_all[i])>=picks[picks_all[i]]: continue
            clst.append(picks_all[i])
            comb(i+1, cnt+1)
            clst.pop()
            
    comb(0,0)
    
    return answer

 

 

• 다른 사람 풀이
  • 하나의 곡괭이를 선택하면 그룹으로 지어서 피로도 계산
  • 다음 곡괭이로는 다음 그룹 계산
  • depth: 전체 곡괭이 수
  • 백트래킹

answer = int(1e9)
    
def solution(picks, minerals):

    def dfs(depth, fatigue,cnt):
        global answer

        if depth == sum(picks):
            answer = min(answer, fatigue)
            return

        for i in range(3):
            if cnt[i] < picks[i]: #곡갱이 제한 확인
                cnt[i] += 1
                plus = cal(depth, i)
                dfs(depth + 1, fatigue + plus, cnt)
                cnt[i] -= 1

                
    def cal(depth, num):
        start = depth * 5
        end = min(start + 5,len(minerals)) #범위 넘어갈 수 있음
        tmp = 0

        for i in range(start, end):
            if minerals[i] == "diamond":
                tmp += [1, 5, 25][num]
            elif minerals[i] == "iron":
                tmp += [1, 1, 5][num]
            else:
                tmp += 1

        return tmp

    cnt = [0, 0, 0] #곡갱이 사용 수
    dfs(0, 0,cnt)
    
    return answer