Lv2. 피로도

코딩테스트 연습 > 피로도

1. 풀이 설명

1. dungeons 의 크기가 최대 8이므로 완전탐색, 순열을 사용하여 문제를 풀었다.

2. dungeons 를 순열로 만들어서 모든 경우에 대해 count 를 계산하고 최대 count 를 반환한다.

   • python: permutations
   • kotlin: dfs

2. 나의 풀이

python

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    for dungeon in permutations(dungeons, len(dungeons)):
        current = k
        count = 0
        for d in dungeon:
            if current >= d[0]:
                current -= d[1]
                count += 1
        answer = max(answer, count)
    return answer

kotlin

class Solution {
    private val visited = BooleanArray(8)
    private var count = 0
    private var answer = 0

    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        for (i in dungeons.indices) {
            dfs(k, i, dungeons)
        }
        return answer
    }

    private fun dfs(k: Int, current: Int, dungeons: Array<IntArray>) {
        for (i in dungeons.indices) {
            if (visited[i].not() && k >= dungeons[i][0]) {
                visited[i] = true
                count += 1
                answer = Math.max(answer, count)
                dfs(k - dungeons[i][1], i, dungeons)
                visited[i] = false
                count -= 1
            }
        }
    }
}

3. 배운점

1. 순열로 완전탐색 풀기

• python 순열

from itertools import permutations

permutations(list, len(list))

• kotlin 순열

fun a() {
	for (i in list.indices) {
    	dfs(i, list)
    }
}

fun dfs(current: Int, list: List) {
	for (i in list.indices) {
    	visited[i] = true
        dfs(i, list)
        visited[i] = false
    }
}