[ 위클리 챌린지 ] [ 12주차 ] 피로도

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

코딩테스트 연습 - 12주차

 

---

풀이 과정

---

1. 던전의 수가 최대 8개까지밖에 없으므로 모든 조합을 다 해보는게 제일 쉬울것이라 판단
2. 배열의 인덱스가 2까지 있다고 하면 가능한 케이스는
   1. (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)
   2. 위 케이스를 하나씩 해보면서 탐험 가능한 최대 던전 수를 갱신하는 방식으로 풀이를 진행하면 된다.
   3. 초기 피로도를 k로 잡고, 현재 던전의 최소 필요 피로도보다 현재 피로도가 클 때, 던전의 수를 하나 늘리고 현재 피로도에서 현재 던전의 소모 피로도를 빼주는 방식으로 진행한다. 물론 최소 필요 피로도가 더 크다면 생략
3. recursion으로 구현하여도 되지만, 파이썬의 permutations 함수를 사용하는것이 가장 간편하다고 생각됨.

---

소스 코드

---

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    total_index = [i for i in range(len(dungeons))]
    total_case = list(permutations(total_index, len(dungeons)))
    
    for each_case in total_case:
        fatigue = k
        dungeon_count = 0
        
        for dungeon_idx in each_case:
            if fatigue >= dungeons[dungeon_idx][0]:
                dungeon_count += 1
                fatigue -= dungeons[dungeon_idx][1]
        
        answer = max(answer, dungeon_count)
    
    return answer