TIL #56

피로도

현재피로도 k, 던전상태2차배열 [던전최소요구피로도, 소모피로도] 가 주어진다. k가 최소피로도 이하이면 던전에 입장하지 못하고 피로도보다 높아 입장한다면 소모피로도만큼 현재피로도가 깎이게 된다. 이때 던전을 최대로 입장할 수 있는 횟수를 구해야한다.

던전의 개수는 1~8개이기 때문에 시간복잡도를 고려하지 않고 DFS(완전탐색) 이용해 구할 수 있다. 시간안에 풀지못해 다른사람의 코드를 참고했다.

---

class Solution {
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        var answer: Int = 0
        answer = dfs(dungeons, BooleanArray(dungeons.size), k, 0, 0)
        return answer
    }
    fun dfs(dungeons: Array<IntArray>,visited: BooleanArray, k: Int, max: Int, cnt:Int):Int{
        var m = max
        for(i in dungeons.indices){
            if(!visited[i] && k >= dungeons[i][0]){
                visited[i] = true
                m = dfs(dungeons, visited, k-dungeons[i][1], m, cnt+1)
                visited[i] = false
            }
        }
        return maxOf(m, cnt)
    }
}

---

다른사람의 풀이

class Solution {
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        var maxN = 0
        for (i in 0 until dungeons.count()) {
            var d = dungeons[i]
            if (k >= d[0]) {
                var subN = solution(
                    k - d[1], 
                    dungeons.sliceArray(0 .. i - 1) + 
                        dungeons.sliceArray(i + 1 .. dungeons.count() - 1))
                if (subN + 1 > maxN) maxN = subN + 1
                if (maxN == dungeons.count()) return maxN
            }
        }
        return maxN
    }
}