[Algorithm / 25.04.04] 프로그래머스 - 피로도

문제 설명

XX게임에는 피로도 시스템(피로도가 0 이상이어야 던전을 탐험할 수 있음)이 있으며, 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있습니다. 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도가 20 소모됩니다.

이 게임에서 던전들을 최대한 많이 탐험하려고 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

 

---

 

내 풀이 과정

 

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    var maxCase = 0
    
    func search(_ remained: [[Int]], _ now: Int, _ count: Int) {
        print("now: \(now)")
        print("remained: \(remained)")
        print("count: \(count)")
        if remained.count == 0, maxCase < count {
                maxCase = count
            }
        
        for i in 0..<remained.count {
            if now < remained[i][0] {
                maxCase = max(maxCase, count)
                continue
            }
        
            var newRemained = remained
            newRemained.remove(at: i)
            
            search(newRemained, now - dungeons[i][1], count + 1)
        }
    }
    
    search(dungeons, k, 0)
    
    return maxCase
}

 

원래 15점이었던거 42점까지 올려서 어 일단 되는건 되나보다 했는데 (솔직히 만년 0점이라 기분 좀 좋았음)

여기서 더 케이스 검증을 해야되는줄 알고 생각해보다가 답 안나와서 오늘 코드카타 시간에 팀원분들한테 공유하면서 고민해보니

 

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    var maxCase = 0
    
    func search(_ remained: [[Int]], _ now: Int, _ count: Int) {
        if remained.count == 0, maxCase < count {
                maxCase = count
            }
        
        for i in 0..<remained.count {
            if now < remained[i][0] {
                maxCase = max(maxCase, count)
                continue
            }
            
            var newRemained = remained
            newRemained.remove(at: i)
            
            search(newRemained, now - remained[i][1], count + 1) // dungeons -> remained
        }
    }
    
    search(dungeons, k, 0)
    
    return maxCase
}

 

 

search 두번째 파라미터에 dungeons를 넣어줬던게 문제였다. 새롭게 꺼낼 부분에 대해선 업데이트 되어야 했던 내용인데 다른 로직에 정신이 없어서 이런 디테일에 신경을 쓰지 못했다. 그나저나 이전에 dfs하면 전혀 엄두도 못냈는데, 이번엔 난이도가 좀 낮긴 해도 재귀함수를 스스로 써볼 수 있는 기회가 되어 좋았다. 

 

+ 아 뭔가 inout을 통해 newRemained를 관리하고 데이터를 초기화해주는 식으로 한다면 좀 더 괜찮은 방법이 되지 않을까 싶다

 

오늘은 성장했다...