프로그래머스 고득점 Kit - 피로도

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

• 현재 체력과 각 던전을 탐험하기 위한 [던전 입장에 필요한 피로도, 소모 피로도] 리스트가 주어진다
• 최대한 많은 던전을 탐험하고자 할때, 최대 탐험할 수 있는 던전 수를 반환해라

Input / Output Example

k	dungeons	result
80	[[80,20], [50,40], [30,10]]	3

 

Solution

나의 경우에는 순열과 중첩반복문을 사용해 $O(n!+t^2)$ 의 시간복잡도가 걸렸다.

순열로 접근한다고 해도, dungeons 리스트의 최대 길이가 크지 않아, 시간 제한에 걸리지 않을 것이라 예상했다.

2025년 2월 23일 기준으로, 가장 오래 걸린 테스트케이스의 소요 시간이 38.59ms 였다 .

 

순열로 모든 던전 입장 경우의 수를 만들어 낸 다음, 

해당 경우의 수를 돌며 입장 가능한 던전의 수를 구한다.

 

그 다음 현재 입장 가능한 던전의 수와 max값을 비교해가며 최대 던전 수를 구한다.

 

Code

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    nPr = permutations(dungeons, len(dungeons))
    for one in nPr:
        hp = k
        turn = 0
        for dungeon in one:
            if hp >= dungeon[0]:
                hp -= dungeon[1]
                turn += 1
            else:
                break
        answer = max(answer, turn)
                
    return answer