[ Programmers ] 87946 / 피로도

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

프로그래머스

 

문제

---

피로도를 사용하여 던전을 탐험할 수 있습니다.

 

각 던전마다 탐험을 시작하기 위해 필요한 최소 필요 피로도와 던전 탐험을 마쳤을 때 소모되는 소모 피로도가 있습니다.

• 최소 필요 피로도: 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
• 소모 피로도: 던전을 탐험한 수 소모되는 피로도

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 존재합니다.

 

한 유저는 이 던전들을 최대한 많이 탐험하려 합니다.

유저의 현재 피로도 k와 각 던전별 최소 필요 피로도, 소모 피로도가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때,

유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

 

 

제한사항

---

• dungeons = [ 최소 필요 피로도, 소모 피로도 ]
• 최소 필요 피로도 ≥ 소모 피로도

 

 

Solve

---

이 문제는 백트리킹으로도 풀 수 있는 문제라고 합니다. (풀어보기)

저는 해당 문제를 순열을 이용하여 풀었습니다. 

 

모든 순서를 구해서 각 case 마다 탐험할 수 있는 던전의 개수를 구해서 최댓값을 찾아주었습니다. 

for p in permutations(dungeons, len(dungeons)):
        print(p)

 

 

Code

---

from itertools import permutations

def solution(k, dungeons):
    
    result = 0
    
    for p in permutations(dungeons, len(dungeons)):
        tmp = k # 주의 
        cnt = 0
        
        for need, spend in p:
            if tmp >= need:
                # 가능 
                tmp -= spend 
                cnt += 1
        result = max(result, cnt)
        
    return result