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

😀요점

해당 문제는 DP 문제이다.

중요 포인트는 다음과 같음

1. 최대 알고력, 코딩력을 찾아 2차원의 DP 배열을 생성할 것
2. 전체 순회하며 알고력, 코딩력이 모두 달성되는 시점의 소요 시간을 반환할 것

😎풀이

function solution(alp, cop, problems) {
    // 목표 알고력, 코딩력 
    let goalAlp = alp
    let goalCop = cop
    // 최대 알고력, 코딩력 할당
    for(const [curAlp, curCop] of problems) {
        if(goalAlp < curAlp) goalAlp = curAlp
        if(goalCop < curCop) goalCop = curCop
    }
    // 소요된 시간
    const history = Array.from(Array(goalAlp + 1), () => Array(goalCop + 1).fill(151));
    history[alp][cop] = 0
    for(let i = alp; i <= goalAlp; i++) {
        for(let j = cop; j <= goalCop; j++) {
            // 알고력, 코딩력을 1증가시키는 최소 시간 구하기
            if(i+1 <= goalAlp) history[i+1][j] = history[i+1][j] < history[i][j]+1 ? history[i+1][j] : history[i][j]+1
            if (j+1 <= goalCop) history[i][j+1] = history[i][j+1] < history[i][j]+1 ? history[i][j+1] : history[i][j]+1;

            const curTime = history[i][j]
            // 목표치 달성 시, 걸린시간 반환
            if(i === goalAlp && j === goalCop) return curTime
            
            // 가능한 방법을 순회하며, 향상된 능력의 인덱스에 소요 시간을 할당해놓음
            for(const [reqAlp, reqCop, incAlp, incCop, t] of problems) {
                if(i < reqAlp || j < reqCop) continue
                
                const resultAlp = goalAlp > i+incAlp ? i+incAlp : goalAlp
                const resultCop = goalCop > j+incCop ? j+incCop : goalCop
                
                history[resultAlp][resultCop] =  history[resultAlp][resultCop] > curTime+t ? curTime+t : history[resultAlp][resultCop]
            }
        }
    }
    
    return 0 
}