프로그래머스 (Level 2) - 피로도

1. 문제 설명

• 일정 피로도를 사용해서 던전을 탐험할 수 있다.
• 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.
• "최소 필요 피로도"는 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도이다.
• "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타낸다.
  • "최소 필요 피로도" 가 80, "소모 피로도"가 20인 던전을 탐험하려면 유저는 남은 피로도는 80 이상이어여 하며 탐험한 후에는 피로도 20이 소모된다.
• 유저의 현재 피로도 k, 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수
• 유조가 탐험할 수 있는 최대 던전수를 return해라.

---

2. 제한사항

• k는 1 이상 5,000 이하인 자연수이다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하이다.
  • dungeons의 가로(열) 길이는 2이다.
  • 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]이다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수이다.
  • 서로 다른 던전의 ["최소 필요 피로도","소모 피로도"]가 서로 같을 수 있다.

3. 입출력 예

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

• 현재 피로도는 80이다.
• 만약, 첫 번째 -> 두 번째 -> 세 번째 던전 순서로 탐험한다면
  1. 현재 피로도는 80이다. 첫 번째 던전도 "최소 필요 피로도"도 80이므로 첫 번째 던전을 탐험할 수 있다. "소모 피로도"는 20이므로 탐험 후 남은 피로도는 60이된다.
  2. 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로 두 번째 던전을 탐험할 수 있다. "소모 피로도"는 40이므로 탐험 후 남은 피로도는 20이다.
  3. 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이다. 하지만 남은 피로도보다 크므로 던전은 탐험할 수 없다.
  4. 총 2번 탐험 가능
• 만약, 첫 번째 -> 세 번째 -> 두 번째 던전 순서로 탐험한다면현재 피로도는 80이다.
  1. 첫 번째 던전도 "최소 필요 피로도"도 80이므로 첫 번째 던전을 탐험할 수 있다. "소모 피로도"는 20이므로 탐험 후 남은 피로도는 60이된다.
  2. 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로 세 번째 던전을 탐험할 수 있다. "소모 피로도"는 10이므로 탐험후 남은 피로도는 50이다.
  3. 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로 두 번째 던전을 탐험할 수 있다. "소모 피로도"는 40이므로 탐험 후 남은 피로도는 10이다.
  4. 총 3번 탐험 가능

---

4. 풀이 접근

1. 모든 경로를 탐색해봐야하는 경우이다. 제한사항에는 던전이 8개미만이므로 순열을 이용하자.
2. 순열을 이용하여 모든 경우의 수를 생성한다.
3. 각 경우의 수마다 "현재의 피로도" >= "최소 피로도"일 경우
   1. 현재 피로도 - 소모 피로도
   2. 던전 탐험한 횟수 + 1
4. 각 경우의수마다 탐험한 횟수가 저장되는데 거기서 가장 많이 탐험한 경우의수를 추출한다. (max)

---

5. 코드

from itertools import permutations
#모든 경우의수 = 순열!

def solution(k,dungeons):
    result = 0
    answer = []

    for permu in permutations(dungeons, len(dungeons)): #dungeons에서 길이만큼 순열생성
        fatigability = k #피로도 설정
        for c, n in permu:
            if (fatigability >= c): #현재 피로도 >= 최소필요도
                fatigability -= n
                result += 1
            else:
                continue
        answer.append(result) #여러가지 경우의 수가 담김
        result = 0


    return max(answer)

• 깊이우선탐색보다 적은수에는 순열이 더 쉬운것 같다..

---

6. 알아둘만한 문법

from itertools import permutations
for permu in permutations(dungeons, len(dungeons)):

• 2차원 배열의 경우에도 순열을 이용해서 원하는 수만큼 생성가능하다.