[programmers] 피로도 - 위클리 챌린지

<피로도>

문제(출처: https://school.programmers.co.kr/learn/courses/30/lessons/87946)

 

 

문제 풀이

   - my solution

from itertools import permutations # 순열

def solution(k, dungeons):
    answer = -1
    
    arr=list(permutations(dungeons, len(dungeons))) # 모든 경우의 수
    for i in arr:
        start=k # init
        cnt=0 # count
        for j in i:
            if start>=j[0]: # 최소 필요 피로도 충족
                start-=j[1] # 피로도 소모
                cnt+=1 # 탐험 가능
            else:
                break
        if cnt>answer: # 탐험할 수 있는 최대 던전 수
            answer=cnt
            
    return answer

 

 

1) 순열을 사용하여 모든 경우의 수 탐색

2) 모든 경우의 수 탐색

  2-1) 최소 필요 피로도를 충족한 경우: 피로도 소모 및 cnt +1

3) 탐험할 수 있는 최대 던전 수로 answer 값 교체

---

생각🤔

 

처음에는 최소 필요 피로도 순으로 정렬해야 할까, 아니면 소모 피로도 순으로 정렬해야 할까

어떤 순으로 정렬해서 해야 할까로 고민했던 것 같다. 

하지만 문제를 읽어보니 최대 던전의 개수는 8개이므로 순열을 사용해도 될 것 같다는 생각에

permutations를 사용하여 모든 경우의 수를 탐색하는 방법으로 구현하였더니 성공할 수 있었다.

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges