[프로그래머스]level2-피로도-Python[파이썬]

문제설명

문제링크

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

알고리즘

permutations 함수를 사용하여 던전을 방문할 수 있는 모든 경우의 수를 구했다.
이 모든 경우의 수를 pm_results에 담고 이 리스트를 for문을 돌면서 각 경우(r)을 탐색했다.
ex) 다음과 같은 던전 리스트가 주어졌을 때 : dungeons = [80, 20], [50, 40], [30, 10]
만일 첫번째 던전 -> 두번째 던전 -> 세번째 던전 순서로 방문한다고 가정해보자.
(즉 : r = ([80, 20], [50, 40], [30, 10]) )
두번째 for문을 이용하여 각 던전(dg)을 방문.

• 현재 피로도(temp_k)가 필요 피로도(dg[0])보다 같거나 큰 경우
  • 해당 던전은 탐험 가능하므로 현재 피로도(temp_k)는 소모 피로도(dg[1])만큼 감소하고 방문 가능 던전 수(cnt)는 1증가한다.
• 현재 피로도(temp_k)가 필요 피로도(dg[0])보다 작은 경우
  • 해당 던전은 탐험 불가능 -> 당연히 뒤에 있는 던전도 탐험 불가능하므로 두번째 for문을 나온다.

이렇게 던전을 다 돈 후(두번째 for문을 다 돌면) r번째 경우의 수를 사용했을 때 방문 가능 던전 수(cnt)와 이전의 다른 경우의 수를 사용했을 때 방문 가능한 최대 던전 수 (max_cnt)를 비교하여 더 큰 값을 max_cnt에 담는다.

• 그리고 만일 이 값(cnt 혹은 max_cnt)이 n과 같다면 즉 모든 던전 방문 가능하다면 이것이 곧 정답이므로 다른 경우의 수를 볼 필요 없이 cnt(혹은 max_cnt)값을 return한다.
• 이 값이 n과 같지 않은 경우 다른 경우의 수도 봐야하므로 첫번째 for문으로 돌아간다.
  --> 이렇게 모든 경우의 수를 탐색한 후(첫번째 for문을 다 돌면), 그 때의 max_cnt값이 최대 방문 가능 던전 수 이므로 이 값을 return한다.

코드

#  ["최소 필요 피로도", "소모 피로도"]
from itertools import permutations as pm
def solution(k, dungeons):
    n = len(dungeons) # 즉 최대 탐험 가능 던전 수
    pm_results = pm(dungeons, n) # n개의 던전들 중 n개 뽑기 (순열)
    max_cnt = 0 # 최대 방문 가능 던전 수
    for r in pm_results: # r : ([80, 20], [50, 40], [30, 10])
        # print(r)
        cnt = 0 # 방문 가능 던전 수
        temp_k = k
        for dg in r: # dg : [80, 20]  --> [50, 40] --> [30, 10]
            need = dg[0]
            somo = dg[1]
            if temp_k >= need: # 현재 피로도가 필요 피로도보다 큰경우 -> 탐험 가능
                temp_k -= somo # -> 현재 피로도는 소모 피로도 만큼 감소
                cnt += 1
            else: # 현재 피로도 < 필요 피로도 --> 탐험 불가능
                break 
        max_cnt = max(max_cnt, cnt)
        # print(cnt)
        # print(max_cnt)
        if cnt == n: # r번째 순서로 탐험했을 때 방문 가능한 던전 수가 최대 던전 수라면 다른 순열 결과를 더 볼 필요없이 cnt를 반환한다. 
            return cnt
    return max_cnt