3/31(일) 오늘의 코테 3 - 피로도

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명 및 접근 방식

 

"피로도" 문제는 완전탐색(브루트포스) 문제입니다.

이 문제에서는 각 던전마다 "최소 필요 피로도"와 "소모 피로도"가 주어지고, 유저가 현재 가진 피로도(k)를 사용해 탐험할 수 있는 최대 던전 수를 찾아야 합니다.

 

1. 문제 설명
* 유저는 하루에 여러 던전을 탐험할 수 있으며, 각 던전을 탐험하기 위해서는 해당 던전의 "최소 필요 피로도" 이상의 피로도를 가지고 있어야 하고, 던전 탐험 후에는 "소모 피로도"만큼 피로도가 감소합니다.
* 유저의 초기 피로도와 각 던전의 "최소 필요 피로도" 및 "소모 피로도"가 2차원 배열로 주어집니다.
* 유저가 탐험할 수 있는 최대 던전 수를 반환해야 합니다.

 

2. 풀이 과정
* 완전 탐색을 이용하여 모든 던전 탐험 순서의 조합을 고려합니다.
* 각 조합에서 유저가 탐험할 수 있는 던전 수를 계산합니다.
- 유저의 현재 피로도가 던전의 "최소 필요 피로도" 이상이면, 해당 던전을 탐험할 수 있습니다.
- 던전을 탐험할 때마다 유저의 피로도는 해당 던전의 "소모 피로도"만큼 감소합니다.
* 가능한 모든 조합 중에서 유저가 탐험할 수 있는 최대 던전 수를 찾아 반환합니다.

 

 

정답 코드

 

from itertools import permutations

def solution(k, dungeons):
    max_dungeon_count = 0  # 탐험할 수 있는 최대 던전 수
    
    # 모든 던전 순서의 조합을 고려
    for dungeon_order in permutations(dungeons, len(dungeons)):
        fatigue = k  # 초기 피로도
        count = 0  # 탐험한 던전 수
        
        for dungeon in dungeon_order:
            min_fatigue, use_fatigue = dungeon  # 최소 필요 피로도, 소모 피로도
            
            # 던전 탐험 가능 여부 확인
            if fatigue >= min_fatigue:
                fatigue -= use_fatigue  # 피로도 감소
                count += 1  # 탐험한 던전 수 증가
            else:
                break  # 더 이상 탐험 불가능하면 중단
                
        max_dungeon_count = max(max_dungeon_count, count)  # 최대 탐험 가능 던전 수 갱신
        
    return max_dungeon_count

 

이 코드는 주어진 모든 던전의 순서 조합을 생성하고, 각 조합에 대해 유저가 탐험할 수 있는 던전 수를 계산합니다.

모든 조합 중에서 가장 많은 던전을 탐험할 수 있는 경우의 던전 수를 최종적으로 반환합니다.

 

 

import하지 않고 재귀로 순열 구현하기

 

def solution(k, dungeons):

    def explore(fatigue, dungeons, count=0):
        # 모든 던전을 탐험할 수 없는 경우, 현재 카운트 반환
        if not dungeons:
            return count
        # 탐험 가능한 던전이 있는지 확인
        can_explore = False
        for dungeon in dungeons:
            if fatigue >= dungeon[0]:
                can_explore = True
                break
        if not can_explore:
            return count


        max_count = count
        
        for i, dungeon in enumerate(dungeons):
            min_fatigue, use_fatigue = dungeon
            if fatigue >= min_fatigue:
                # 던전을 탐험하고, 남은 던전 리스트에서 현재 던전을 제외
                next_dungeons = dungeons[:i] + dungeons[i+1:]
                # 재귀적으로 다음 던전 탐험 시도
                explored_count = explore(fatigue - use_fatigue, next_dungeons, count + 1)
                if explored_count > max_count:
                    max_count = explored_count
        return max_count

    return explore(k, dungeons)

 

이 코드는 던전 탐험 가능 여부를 확인하는 부분에서 직접 조건을 검사합니다.

각 던전을 순회하며, 현재 피로도로 탐험할 수 있는지 여부를 체크합니다.

만약 탐험할 수 있는 던전이 있다면 해당 던전을 탐험하고, 재귀적으로 남은 던전에 대해 같은 과정을 반복합니다.

이렇게 하여, 모든 가능한 던전 탐험 조합을 고려하고, 최대로 탐험할 수 있는 던전의 수를 계산합니다.