📑문제 개요
던전을 탐험할 때, 주어진 피로도 조건을 만족하면서 탐험할 수 있는 최대 던전 수를 구하는 문제입니다.
✏️문제 제약 조건:
각 던전은 "최소 필요 피로도"와 "소모 피로도"를 가집니다.
"최소 필요 피로도"를 만족해야 던전 탐험이 가능하며, 탐험 후 "소모 피로도"만큼 피로도가 줄어듭니다.
탐험할 수 있는 던전 순서는 자유롭게 선택할 수 있습니다.
🔎문제 접근
핵심 아이디어: 모든 경우의 수 탐색 (완전 탐색)
던전 순서 결정:
던전 순서에 따라 결과가 달라질 수 있으므로, 가능한 모든 순서를 탐색해야 합니다.
이는 순열(permutation)을 사용하여 해결합니다.
던전 탐험 시뮬레이션:
각 순서대로 던전을 탐험하며 탐험 가능한 던전 수를 계산합니다.
최대 던전 수 업데이트:
각 탐색 결과 중 최대 던전 수를 업데이트합니다.
💻코드 구현
import Foundation
func solution(_ k: Int, _ dungeons: [[Int]]) -> Int {
var maxCount = 0 // 탐험 가능한 최대 던전 수
// 1. 순열 생성 함수
func permute(_ array: [[Int]], _ depth: Int) {
if depth == array.count {
maxCount = max(maxCount, simulate(k, array))
return
}
var array = array
for i in depth..<array.count {
array.swapAt(depth, i)
permute(array, depth + 1)
array.swapAt(depth, i) // 원상 복구
}
}
// 2. 던전 탐험 시뮬레이션 함수
func simulate(_ k: Int, _ order: [[Int]]) -> Int {
var fatigue = k // 남은 피로도
var count = 0 // 탐험한 던전 수
for dungeon in order {
let required = dungeon[0]
let consume = dungeon[1]
if fatigue >= required {
fatigue -= consume
count += 1
} else {
break
}
}
return count
}
// 3. 순열을 사용해 모든 경우 탐색
permute(dungeons, 0)
return maxCount
}📝코드 설명
1. 순열 생성 (permute 함수)
주어진 던전 순서를 모든 경우로 나열합니다.
swapAt을 사용하여 현재 인덱스와 다음 인덱스를 교환하며, 모든 순서를 탐색합니다.
순서가 완성되면 simulate 함수를 호출하여 던전 탐험을 시뮬레이션합니다.
2. 던전 탐험 시뮬레이션 (simulate 함수)
입력된 던전 순서대로 탐험합니다.
현재 피로도가 "최소 필요 피로도"보다 크거나 같다면 탐험하고, "소모 피로도"를 피로도에서 차감합니다.
탐험 가능한 던전 수를 반환합니다.
3. 최대 던전 수 업데이트
각 탐험 결과에서 반환된 던전 수를 maxCount와 비교하여 최대값을 유지합니다.
🐧입출력 예시
let k = 80
let dungeons = [[80, 20], [50, 40], [30, 10]]
print(solution(k, dungeons)) // 3과정:
모든 던전 순서를 생성:
[[80, 20], [50, 40], [30, 10]]
[[80, 20], [30, 10], [50, 40]]
[[50, 40], [80, 20], [30, 10]] ... 등.
각 순서별 탐험:
첫 번째 순서: 탐험 가능 → 3개.
두 번째 순서: 탐험 가능 → 3개.
...
결과: 최대 탐험 던전 수는 3.
🐧시간 복잡도
순열 생성:
던전 개수 n에 대해 순열의 시간 복잡도는 O(n!).
최대 8! = 40,320으로 제한된 범위 안에서 충분히 가능.
시뮬레이션:
각 순열당 최대 n의 시간.
O(n × n!) = O(n × (n-1) × ... × 1).
🐧학습 포인트
완전 탐색 (Brute Force):
가능한 모든 경우를 시도해야 하는 문제에서 순열을 활용한 완전 탐색의 중요성을 이해했습니다.
순열 생성:
swapAt과 재귀를 활용해 효율적으로 순열을 생성하는 방법을 배웠습니다.
탐욕 알고리즘과의 차이:
던전을 탐험하는 최적의 순서를 찾기 위해 탐욕 알고리즘 대신 완전 탐색을 사용해야 했음을 깨달았습니다.
▶ 다른 문제 보러가기
