피로도
❓ 문제설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
🚫 제한조건
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
✔ 입출력 예
| k | dungeons | result |
| 80 | [[80,20],[50,40],[30,10]] | 3 |
💡 풀이
function solution(k, dungeons) {
// 내 풀이
let answer = 0
const func = (dungeons, index, fatigue, count) => {
if (dungeons.length === 0) {
answer = answer < count ? count : answer
return
}
const [need, use] = dungeons.splice(index, 1)[0]
if (k - fatigue >= need) {
fatigue += use
count++
}
dungeons.forEach((_, index, arr) => {
func(arr, index, fatigue, count)
})
}
dungeons.forEach((_, index, arr) => {
func(arr, index, 0, 0)
})
return answer
// 다른사람 풀이 참고
// 던전을 탐험 못하는 경우 제외하고 탐색
let answer = 0
const visit = new Array(dungeons.length).fill(false)
const dfs = (k, count) => {
answer = Math.max(answer, count)
for(let i=0; i < visit.length; i++) {
const [need, use] = dungeons[i]
if (!visit[i] && k >= need) {
visit[i] = true
dfs(k - use, count + 1)
visit[i] = false
}
}
}
dfs(k, 0)
return answer
}📝 해설
재귀함수를 사용하여 0번째 index의 던전부터 차례로 모든 던전을 탐색하여 가장 많은 방문 횟수를 리턴하는 func 을 만들었다. (dfs)
이후 다른 풀이를 보니 나와 차이점이 있었는데 나의 풀이는 중간에 탐색을 못하더라도 이 후 과정을 진행하였는데 다른 풀이에서는 그 과정을 생략하였다. 1,2,3,4 던전이 있고 1번 던전을 탐험하고 이후 과정을 탐색하고 있는 과정일 때 2번이 불가능한 상황을 가정한다면, 나의 풀이는 1 -> 2(카운트 x) -> 3 or 4 -> ... (1) 의 과정을 진행 하고 다시 1 -> 3 -> 2 or 4 -> ... (2) 과정을 진행하는데 (1) 과 (2) 과정이 중복되는 것을 알 수 있다. 결과적으로 중간에 피로도의 제약으로 탐험을 못하는 경우 그 이후 상황을 생략하고 다음 탐색으로 넘어 가더라도 결국 그 이후 상황과 동일한 과정도 탐색을 한다는 것을 알 수 있다.
📚 참고자료
- https://kimby.tistory.com/48 (Array 메소드)
