프로그래머스 광물캐기 python

 

프로그래머스

1. 처음에 완전탐색으로 문제를 풀 수 있을 것 같았지만 15! 만큼 시간 복잡도가 나와서 시간초과가 나왔다.

2. 완전 탐색 풀이를 수정 + dfs 함수 사용해서 시간 복잡도를 줄여야했다.

3가지 곡쾡이가 존재 + 최대 광물은 50개. 1 곡쾡이당 5번 사용가능하므로, 50//5 == 10개를 뽑으면 된다.

그렇다면, 최대 대략 3^10만큼의 경우의 수가 나오므로, 시간 제한에 걸리지 않을 것이라 판단할 수 있다.

그래프로 그려보기

코드

answer = int(1e9)
def dfs(total,p_count,m_index,minerals,picks,fatigue):
    global answer
    #광물 다 캤거나 곡쾡이를 다 썼을때 종료
    
    if total == p_count or len(minerals) <= m_index:
        print(fatigue)
        answer = min(answer,fatigue)
        return
    for i in range(len(picks)):
        if picks[i] > 0:
            picks[i] -= 1
            tmp = 0 # 피로도 계산을 합칠 변수
            index = 0# 다음으로 캘 광물 배열의 인덱스를 저장할 변수
            for j in range(m_index,m_index+5):
                index = j
                if j == len(minerals):# 중간에 광물을 다 캐버렸을 경우.
                    break
                    
                if i == 0:# 다이아 곡쾡이일때
                    tmp += 1
                    
                elif i == 1:
                    if minerals[j] == 'diamond':
                        tmp += 5
                    else:
                        tmp += 1
                elif i == 2:
                    if minerals[j] == 'diamond':
                        tmp += 25
                    elif minerals[j] == 'iron':
                        tmp += 5
                    else:
                        tmp += 1
                
            dfs(total,p_count+1,index+1,minerals,picks,fatigue+tmp)
            picks[i] += 1
def solution(picks, minerals):
    total = sum(picks)
    dfs(total,0,0,minerals,picks,0)
    return answer

 

참고

 

프로그래머스_광물캐기_level2(python)