프로그래머스 | Python | 완전탐색 | 피로도 (Lv.2)

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

프로그래머스

문제 해결: 완전탐색을 통한 던전 탐험

Python 코드

from itertools import permutations

def solution(k, dungeons):
    max_dungeons = 0

    # 던전 순서의 모든 경우의 수를 생성
    for order in permutations(dungeons, len(dungeons)):
        current_k = k  # 현재 피로도
        count = 0      # 탐험 가능한 던전 수

        # 주어진 순서대로 던전을 탐험
        for dungeon in order:
            required, consumption = dungeon  # 최소 필요 피로도, 소모 피로도
            if current_k >= required:        # 탐험 가능 여부 확인
                current_k -= consumption     # 피로도 소모
                count += 1                   # 탐험 수 증가
            else:
                break  # 피로도가 부족하면 탐험 중단

        # 최대 탐험 가능한 던전 수 갱신
        max_dungeons = max(max_dungeons, count)

    return max_dungeons

---

코드 해설

1. 던전 순서를 고려한 완전탐색

• 문제에서 주어진 던전 순서를 재배치할 수 있습니다.
• itertools.permutations를 사용해 던전 순서의 모든 경우의 수를 생성.
  permutations 사용법 참고: https://mkdiriandev.tistory.com/56 
  •   예: dungeons = [[80, 20], [50, 40], [30, 10]]
    •   가능한 순서:
    •   [[80, 20], [50, 40], [30, 10]] [[80, 20], [30, 10], [50, 40]] [[50, 40], [80, 20], [30, 10]] ...

2. 현재 피로도로 탐험 가능한지 확인

• 탐험하려는 던전의 "최소 필요 피로도"를 만족하는지 확인:

if current_k >= required:
    current_k -= consumption  # 피로도 소모
    count += 1                # 탐험 가능 던전 수 증가
else:
    break  # 탐험 중단

3. 최대 던전 수 갱신

• 각 순서에서 탐험 가능한 던전 수를 계산한 뒤, 최대값을 업데이트:

max_dungeons = max(max_dungeons, count)

4. current_k와 count의 위치

current_k와 count의 위치가 for order in permutations(dungeons, len(dungeons)) 반복문 안에 설계된 이유는 각 탐험 순서별로 독립적인 상태를 유지하기 위해서입니다.

왜 current_k와 count가 반복문 안에 위치해야 할까?

1. 탐험 순서별로 독립적인 상태 유지

• 각 탐험 순서(order)는 서로 독립적으로 탐험 가능한 던전을 계산해야 합니다.
• current_k와 count는 각각의 탐험 순서마다 초기화되어야 합니다:
  •   current_k: 탐험을 시작할 때 유저의 초기 피로도(k)로 초기화.
  •   count: 각 탐험 순서에서 탐험한 던전 수를 카운트하기 위해 초기화.

---

핵심 포인트

1. 완전탐색의 필요성
   •   던전 순서에 따라 탐험 가능한 최대 던전 수가 달라질 수 있습니다.
   •   모든 경우의 수를 시도해야 최적의 해답을 찾을 수 있습니다.
2. 순열(Permutations)을 활용한 순서 변경
   •   던전의 개수가 최대 8개이므로 순열을 생성해도 연산량이 충분히 manageable합니다.
   •   최대 경우의 수: 8!=40,320.
   •   8!=40,3208! = 40,320
3. 탐험 조건
   •   현재 피로도(current_k)가 최소 필요 피로도(required) 이상이어야 탐험 가능.
   •   피로도 소모 후 다음 던전으로 이동.
4. 최대값 갱신
   •   모든 경우의 수에서 탐험 가능한 던전 수를 비교하여 최댓값을 찾습니다.

---

문법

언패킹의 동작

예제

dungeon = [80, 20]  # 던전 정보: 최소 필요 피로도, 소모 피로도
required, consumption = dungeon
print(required)     # 80
print(consumption)  # 20

• dungeon 리스트의 첫 번째 값 80은 required에 할당됩니다.
• dungeon 리스트의 두 번째 값 20은 consumption에 할당됩니다.

---

코드 흐름

입력 데이터

k = 80
dungeons = [[80, 20], [50, 40], [30, 10]]

1. k = 80: 초기 피로도.
2. dungeons: 탐험 가능한 던전 정보.
3. 코드가 탐험 순서를 생성한 뒤, 각각의 순서를 탐험하고 가능한 최대 던전 수를 계산합니다.

---

순서별 흐름: 예제

첫 번째 순서: order = [[80, 20], [50, 40], [30, 10]]

1. 초기 상태:
   •   current_k = 80
   •   count = 0
2. 첫 번째 던전 [80, 20]:
   •   required = 80, consumption = 20
   •   current_k(80) >= required(80) 조건 만족 → 탐험 가능.
   •   피로도 차감: current_k -= consumption → 80 - 20 = 60.
   •   탐험한 던전 수 증가: count += 1 → count = 1.
3. 두 번째 던전 [50, 40]:
   •   required = 50, consumption = 40
   •   current_k(60) >= required(50) 조건 만족 → 탐험 가능.
   •   피로도 차감: current_k -= consumption → 60 - 40 = 20.
   •   탐험한 던전 수 증가: count += 1 → count = 2.
4. 세 번째 던전 [30, 10]:
   •   required = 30, consumption = 10
   •   current_k(20) < required(30) 조건 불만족 → 탐험 불가능.
   •   break 실행:
     •   현재 반복문(for dungeon in order)을 중단하고, 다음 순서의 탐험으로 이동.
5. 최대 던전 수 갱신:
   •   탐험 종료 후 max_dungeons = max(max_dungeons, count) 실행.
   •   max_dungeons = max(0, 2) = 2.

---

두 번째 순서: order = [[80, 20], [30, 10], [50, 40]]

1. 초기 상태:
   •   current_k = 80
   •   count = 0.
2. 첫 번째 던전 [80, 20]:
   •   조건 만족 → 탐험 가능.
   •   피로도 차감: current_k = 60.
   •   탐험 수 증가: count = 1.
3. 두 번째 던전 [30, 10]:
   •   조건 만족 → 탐험 가능.
   •   피로도 차감: current_k = 50.
   •   탐험 수 증가: count = 2.
4. 세 번째 던전 [50, 40]:
   •   조건 만족 → 탐험 가능.
   •   피로도 차감: current_k = 10.
   •   탐험 수 증가: count = 3.
5. 최대 던전 수 갱신:
   •   탐험 종료 후 max_dungeons = max(max_dungeons, count) 실행.
   •   max_dungeons = max(2, 3) = 3.

---

break의 동작

1. break가 발생하는 시점:
   •   조건 current_k >= required가 만족되지 않을 때 실행.
   •   현재 던전 탐험이 불가능하면, 더 이상 반복문을 진행하지 않고 바로 종료.
2. break 이후 동작:
   •   현재 탐험 순서(for dungeon in order)를 중단.
   •   다음 탐험 순서로 넘어감(for order in permutations(dungeons, len(dungeons))).

---

코드 흐름 전체 예제 출력

k = 80
dungeons = [[80, 20], [50, 40], [30, 10]]

print(solution(k, dungeons))

출력:

3

---

주요 동작 요약

1. 각 탐험 순서를 생성하고 반복 실행.
2. 탐험 순서 내에서 피로도를 확인하여 가능한 던전만 탐험.
3. break로 반복문을 중단한 뒤 다음 탐험 순서로 이동.
4. 모든 순서를 탐험한 뒤 최대 던전 수를 반환.