[Swift] 프로그래머스 위클리 챌린지 피로도

 

Problem

 

코딩테스트 연습 - 피로도

---

Solution

 

해당 문제는 백트래킹으로 풀어야 하는 문제입니다.

 

(혹시 백트래킹을 모르시는 분들은 여기 에서 보고 와주세요!)

 

answer를 0부터 탐험을 시작해줍니다.

 

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var answer:Int = 0
    explore(dungeons: dungeons, answer: &answer, k:k, count: 0)
    return answer
}

 

던전들을 순회하며 최소 필요 피로도(dungeon[0])와 소모 피로도(dungeon[1])보다 현재 피로도(k)가 큰지 비교해줍니다.

 

만약 조건에 부합하다면 새로운 피로도인 새로운 피로도(newK)를 만들어주고 현재 피로도(k)에서 소모 피로도(dungeon[1])를 빼줍니다.

 

그리고 던전들에서 조건에 부합한 던전을 삭제하고 갯수(count)를 하나 늘려준 뒤 재귀해줍니다.

 

explore를 재귀하면서 가장 많은 갯수를 저장할 answer와 count를 비교해 더 큰 값으로 answer를 변경해줍니다.

 

func explore(dungeons:[[Int]],answer:inout Int,k:Int,count:Int) {
    answer = max(answer,count)
    for (i,dungeon) in dungeons.enumerated() {
        var newDungeons:[[Int]] = dungeons
        if dungeon[0] <= k && dungeon[1] <= k{
            let newK = k - dungeon[1]
            newDungeons.remove(at: i)
            explore(dungeons:newDungeons,answer: &answer,k: newK,count: count + 1)
        }
    }
}

---

Source Code