프로그래머스 - 피로도(Swift)

프로그래머스 - 피로도(Swift)

 

 

 문제 설명

 

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 나의 풀이

 

던전의 개수가 최대 8개이기 때문에 전체를 탐색해도 된다고 생각했다.

이를 DFS로 구현했는데 check배열을 통해서 갔던 곳은 탐색하지 못하게 설정했다. 

 

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    func DFS(_ L: Int, _ leftedHP: Int, _ sum: Int) {
        if sum > cnt {
            cnt = sum
        }
        for i in 0..<dungeons.count {
            if ch[i] == false {
                if leftedHP >= dungeons[i][0] {
                    ch[i] = true
                    DFS(L+1, leftedHP-dungeons[i][1], sum+1)
                    ch[i] = false
                }
            }
        }
    }
    
    var cnt = 0
    var ch = [Bool](repeating: false, count: dungeons.count)
    DFS(0, k, 0)
    
    return cnt
}

 

글을 적으면서 sum변수가 꼭 필요한지에 대해 생각했고 결국 지우고 이 코드에서는 깊이가 곧 담을 수 있는 개수이기 때문에 L과 cnt를 비교해서 답을 넣어주었다.

 

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    func DFS(_ L: Int, _ leftedHP: Int) {
        if L > cnt {
            cnt = L
        }
        for i in 0..<dungeons.count {
            if ch[i] == false {
                if leftedHP >= dungeons[i][0] {
                    ch[i] = true
                    DFS(L+1, leftedHP-dungeons[i][1])
                    ch[i] = false
                }
            }
        }
    }
    
    var cnt = 0
    var ch = [Bool](repeating: false, count: dungeons.count)
    DFS(0, k)
    
    return cnt
}