[프로그래머스] Lv 2. 피로도

코딩테스트 연습 - 피로도

 

문제

일정 피로도를 사용해서 던전을 탐험할 수 있습니다.

이 때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려고 합니다.

현재 피로도 k와 각 던전별 "최소 필요 필요도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때,

유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

풀이

반복문의 주체가 되는 dungeons 배열이 매우 작습니다.(최대 8개)

때문에 모든 경우의 수를 확인하는 완전탐색으로 풀어도 가능할 듯 합니다.

 

코드

import kotlin.math.*

class Solution {
    var answer = 0
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        val visited = BooleanArray(dungeons.size)
        solve(k, 0, dungeons, visited)
        return answer
    }
    
    fun solve(
        k: Int, // 남은 피로도
        result: Int, // 현재까지 완료한 던전 개수
        dungeons: Array<IntArray>, // 던전 정보
        visited: BooleanArray // 던전 방문 여부
    ) {
        answer = max(answer , result)
        for (i in 0 until dungeons.size) {
            // 아직 방문하지 않은 던전이면서 피로도 가능
            if (visited[i].not() && k >= dungeons[i][0]) {
                visited[i] = true
                solve(k-dungeons[i][1],result+1,dungeons,visited)
                visited[i] = false
            }
        }
    }
}