1. 문제 설명

코딩 테스트 공부

2. 문제 분석

알고력, 코딩력을 통해 현재 풀 수 있는 문제에 드는 비용의 최솟값을 갱신해나가자. 알고력과 코딩력을 이중 반복문을 통해 하나씩 확인하면서 업데이트마다 모든 문제를 확인해야 한다는 게 시간 복잡도가 높아지는 이슈. 값 갱신이 일어날 때에만 이후 업데이트를 하도록 했다.

• dp 값을 초기화할 때 INF 값을 Int.max로 설정하면 시간 초과가 난다. 문제에서 주어진 문제의 최대 개수 * 비용인 10000으로 최대 시간을 설정했더니 시간 초과는 나지 않았다.

3. 나의 풀이

import Foundation

func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
    let maxAlp = problems.map{$0[0]}.max()!
    let maxCop = problems.map{$0[1]}.max()!
    let alp = min(alp, maxAlp)
    let cop = min(cop, maxCop)
    let INF = 10000
    var dp = Array(repeating: Array(repeating: INF, count: maxCop + 1), count: maxAlp + 1)
    dp[alp][cop] = 0
    
    for a in alp..<maxAlp+1 {
        for c in cop..<maxCop+1 {
            var flag = false

            if a + 1 <= maxAlp {
                dp[a+1][c] = min(dp[a+1][c], dp[a][c] + 1)
                flag = true
            }
            if c + 1 <= maxCop {
                dp[a][c+1] = min(dp[a][c+1], dp[a][c] + 1)
                flag = true
            }
            
            if flag {
                for problem in problems {
                let (alp_req, cop_req, alp_rwd, cop_rwd, cost) = (problem[0], problem[1], problem[2], problem[3], problem[4])
                
                if a >= alp_req && c >= cop_req {
                    let totalAlp = min(maxAlp, a + alp_rwd)
                    let totalCop = min(maxCop, c + cop_rwd)
                    dp[totalAlp][totalCop] = min(dp[totalAlp][totalCop], dp[a][c] + cost)
                    }
                }
            }
        }
    }
    return dp[maxAlp][maxCop]
}