[고득점 Kit / 완전탐색] 피로도

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

프로그래머스

 

이 문제를 푸는 흐름은 다음과 같다.

 

1. permutations(dungeons)는 던전들의 가능한 모든 순서를 생성한다.

 

2. 각 순서에 대해, 주어진 k 값에서 시작하여 던전마다 탐험할 수 있는지 확인하고, 탐험할 수 있다면 피로도를 차감하고 탐험한 던전 수를 증가시킨다.

 

3. 던전 탐험이 끝난 후 최대 탐험 던전 수를 갱신한다.

 

이를 코드로 옮겨보면 다음과 같다.

 

 

 

from itertools import permutations

def solution(k, dungeons):
    max_dungeons = 0
    
    for perm in permutations(dungeons):
        current_fatigue = k
        count = 0
        
        for min_fatigue, use_fatigue in perm:
            if current_fatigue >= min_fatigue:
                current_fatigue -= use_fatigue
                count += 1
            else:
                break

        max_dungeons = max(max_dungeons, count)
    
    return max_dungeons

 

 

여기서 순열을 사용하는 부분에 대해서 좀 더 자세히 알아보자.

 

for perm in permutations(dungeons):
    current_fatigue = k
    count = 0

 

 

• permutations(dungeons):
  • itertools.permutations 함수는 주어진 리스트(여기서는 dungeons)의 모든 순서를 생성해준다.
  • 예를 들어, 던전이 3개 있을 때, 각 던전을 탐험하는 순서는 여러 가지가 있을 수 있다. 첫 번째 던전으로 어떤 것을 선택하느냐에 따라 두 번째, 세 번째 순서가 달라질 수 있다.
  • 예를 들어 dungeons = [[80, 20], [50, 40], [30, 10]]라는 던전 배열이 있으면, permutations(dungeons)는 다음과 같은 순서들을 모두 만든다.
    • [(80, 20), (50, 40), (30, 10)]
    • [(80, 20), (30, 10), (50, 40)]
    • [(50, 40), (80, 20), (30, 10)]
    • [(50, 40), (30, 10), (80, 20)]
    • [(30, 10), (80, 20), (50, 40)]
    • [(30, 10), (50, 40), (80, 20)]
  • 이런 식으로 가능한 모든 순서를 생성해준다.
• current_fatigue = k:
  • 각 순서를 시도할 때마다, 유저가 가진 **현재 피로도(current_fatigue)**는 처음 주어진 k로 다시 초기화된다.
  • 이는 던전을 순서대로 탐험할 때마다 피로도가 줄어드는데, 순서를 새로 시도할 때마다 처음 피로도로 돌아가야 하기 때문이다.
• count = 0:
  • 탐험한 던전의 수를 세는 변수다. 매번 새로운 순서를 시도할 때마다 던전을 몇 개 탐험했는지를 카운트하는데, 순서를 새로 시도할 때는 당연히 처음부터 다시 탐험을 시작하므로 count도 0으로 초기화된다.

 

그리고 각 경우의 수에 따른 던전 탐험 횟수를 센다. 마지막으로, 던전 탐험횟수가 이전에 계산했던 count값보다 크면, 값을 갱신한다.

for min_fatigue, use_fatigue in perm:
            if current_fatigue >= min_fatigue:
                current_fatigue -= use_fatigue
                count += 1
            else:
                break

max_dungeons = max(max_dungeons, count)