[프로그래머스] 코딩 테스트 공부

문제

프로그래머스

입력

alp:Int = 최초 알고력 
cop:Int = 최초 코딩력
problems:[[Int]] = problem의 배열   , 길이는 ≤ 6. 

problem = [alp_req, cop_req, alp_rwd, cop_rwd, cost]

alp_req는 문제를 푸는데 필요한 알고력입니다.
0 ≤ alp_req ≤ 150

cop_req는 문제를 푸는데 필요한 코딩력입니다.
0 ≤ cop_req ≤ 150

alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
0 ≤ alp_rwd ≤ 30

cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
0 ≤ cop_rwd ≤ 30

cost는 문제를 푸는데 드는 시간입니다.
1 ≤ cost ≤ 100

결과

answer: Int = 모든 문제를 풀었을 때 최소 시간

해석

입력이 크게 길지 않고 알고력과 코딩력의 범위가 크지 않으므로 DP를 의심할 수 있다.

생각보다 DP 점화식은 문제에서 직관적으로 나왔다.

 

조건은 다음과 같다. 

 

1. 알고력과 코딩력을 키우는 방법은 크게 2가지이다.

• 자습을 통해 알고력 또는 코딩력을 1 성장시킬수 있다, 비용 = 1시간 
• 해당 문제를 푼다.  alp_rwd 와 cop_rwd 만큼의 알고력과 코딩력을 얻늗다, 비용 cost 시간

2. 해당 문제를 풀 때 alp_req와 cop_req을 보다 크거나 같아야 문제를 풀 수 있다.

 

이게 끝이다.

 

그러면 점화식은 다음과같다 . 

 

dp[alp][cop] = 현재 alp cop 상태일 때 최소 시간  

코드

import Foundation

func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
    
    // 모든 문제를 풀어야함 
    
    var maxAlp: Int = 0 // 최대 Alp
    var maxCop: Int = 0 // 최대 Cop
    
    for problem in problems {
        maxAlp = max(maxAlp,problem[0])
        maxCop = max(maxCop,problem[1])
    }
    
    // 초기 상태 초기화
    var alp = min(maxAlp,alp) 
    var cop = min(maxCop,cop)
    
    var dp:[[Int]] = [[Int]](repeating:[Int](repeating:1000000, count: maxCop+2), count: maxAlp+2) 
    
    // dp[alp][cop] =  현재 alp와 cop 도달 시 최소 시간 
    
    // 알고력과 코딩력을 올리는 방법은 다음과 같다.
    // 1. 개인 공불르 통해 알고력 또는 코딩력을 1 증가 시킬 수 있다.
    // 2. 현재 문제를 풀어 reward로 얻을 수 있다. 
    
     dp[alp][cop] = 0 // 초기는 푼 문제와 걸린 시간이 없으므로 0 
    
    for i in alp...maxAlp {
        for j in cop...maxCop {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1) // 1시간 투자해서 알고력 높이기
            dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1) // 1시간 투자해서 코딩력 높이기 
            
            // 현재 i,j의 알고력과 코딩력 일 때 문제 도전
            for problem in problems {
                let aReq = problem[0]
                let cReq = problem[1]
                let aRew = problem[2]
                let cRew = problem[3]
                let cost = problem[4]
                
                if i >= aReq && j >= cReq { // 모든 조건을 만족할 때 
                    let nextAlp = min(maxAlp,i + aRew)
                    let nextCop = min(maxCop,j + cRew)
                    
                    dp[nextAlp][nextCop] = min(dp[nextAlp][nextCop], dp[i][j] + cost)  
                }

            }
            
        }
    }
    

    return dp[maxAlp][maxCop]
}