[프로그래머스] 피로도

1. 문제 이해

던전마다 최소 필요 피로도와 소모 피로도가 있다.

현재 피로도가 최소 필요 피로도 이상이어야 던전에 입장할 수 있고, 탐험하면 소모 피로도만큼 줄어든다.

현재 피로도 k로 탐험할 수 있는 최대 던전 수를 리턴한다. (던전은 최대 8개)

 

 

2. 풀이 과정

던전을 도는 순서에 따라 결과가 달라지고, 정렬 기준만으로는 최적 순서를 보장할 수 없다.(그리디 방식)

그래서 모든 순서를 시도하는 완전탐색(브루트포스)으로 푼다.

 

던전이 최대 8개라서 가능한 순서는 8! = 40,320가지다.

itertools.permutations로 모든 순서를 만들고, 순서마다 피로도를 k로 초기화한 뒤 던전을 차례로 돈다.

 

현재 피로도가 최소 필요 피로도 이상이면 소모 피로도만큼 빼고 개수를 센다. 모든 순서 중 센 개수의 최댓값이 답이다.

 

 

3. 전체 코드

import itertools

def solution(k, dungeons):
    answer = -1
    for order in itertools.permutations(dungeons):
        cur = k # k로 초기화
        cnt = 0
        
        for need, cost in order:
            if cur >= need:
                cur -= cost
                cnt += 1
        
        answer = max(answer, cnt)
    
    return answer

 

 

4. 생각할 점

- itertools.permutations()를 사용해서 모든 순서에 대해 완전 탐색을 진행한다는 발상

 

 

5. 출처

- https://school.programmers.co.kr/learn/courses/30/lessons/87946