문제

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

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

from itertools import permutations

def solution(k, dungeons):
    
    answer = 0
    dungeons = list(permutations(dungeons, len(dungeons)))
    pirodo = k
    
    for dungeon in dungeons: # 테스트 케이스의 경우 6번 반복 
        
        # 피로도와 던전 입장 횟수는 계속 초기화
        k = pirodo # 피로도
        cnt = 0 # 던전 입장 횟수
        
        for need, use in dungeon:
            
            if k >= need:
                k -= use
                cnt += 1
        
        answer = max(answer, cnt)

    return answer
    

설명

처음 생각했던것은 '최소 필요 피로도'를 내림차순하고 '소모 피로도'를 오름차순 으로 정렬해서 던전 입장 횟수를 세는 것이었다. 근데 이 경우에는 3번 던전을 입장하지 못하게 되서 수정해야 했고 순열과 조합이라는 힌트를 얻어서 풀었다.

결국은 순열을 이용해서 완전탐색 으로 던전 입장 횟수를 센 다음 최댓값을 계속 갱신해나가면 된다.

다시 풀이한 코드

from itertools import permutations

def solution(k, dungeons):
    
    answer = 0
    n = len(dungeons)
    dungeons = list(permutations(dungeons, n)) # 던전에 입장하는 모든 경우의 수
        
        
    for dungeon in dungeons:
        
        pirodo = k # 모든 경우의 수에 대하여 반복문을 돌리므로 다음 반복문 시작전 피로도 초기화
        clear = 0 # 던전을 클리어 한 횟수
        
        for need, consume in dungeon:
            
            if pirodo >= need: # 현재 피로도가 '최소 필요 피로도' 보다 크거나 같으면 던전 입장
                pirodo -= consume
                clear += 1
            
        answer = max(answer, clear)            
    
    return answer
    

다시 풀었지만 원래 정답으로 풀었던 코드와 다른건 없다.

참고자료

X