[코딩테스트] 피로도

문제

• 일정 피로도를 사용해 던전을 탐험할 수 있다. 각 던전마다 탐험을 시작하기 위해 필요한 '최소 필요 피로도'와 던전 탐험을 마쳤을 대 소모되는 '소모 피로도'가 있다. 
• 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 탐험할 수 있는 던전의 최대 개수 구하기
  • 1  <= 유저의 현재 피로도 <= 5000
  • 1 <= 던전 개수 <= 8

 

풀이

• 각 던전 별로 탐험의 경우의 수는 최대 8! 이고, 각 던전을 탐험할 때와 하지 않을 때 2가지 경우로 나눌 수 있으므로 총 경우의 수는 $8! * 2^8$ 개가 된다. 약 천 만개의 경우의 수 이므로 모두 탐색할 수 있다.
• DFS 이용해 각 경우의 수를 탐색한다.

 

answer = 0

def dfs(now, dungeons, cnt) :
    global answer
    if not len(dungeons):   # 던전을 모두 확인한 경우
        answer = max(answer, cnt)
        return
    
    for i, d in enumerate(dungeons) :
        # 최소 피로도 충족시 던전 탐험
        if d[0] <= now :        
            dfs(now-d[1], dungeons[:i]+dungeons[i+1:], cnt+1)
        # 던전 탐험하지 않음
        dfs(now, dungeons[:i]+dungeons[i+1:], cnt)

def solution(k, dungeons):
    # 최소 피로도가 높고, 소모 피로도가 낮은 순서대로 정렬
    dungeons = sorted(dungeons, key=lambda x : (-x[0], x[1]))
    dfs(k, dungeons, 0)
        
    return answer

 

References

• 프로그래머스 고득점Kit 완전탐색