[JS] 코딩테스트 공부

처음에 문제를 보자마자 dp..? 라는 생각이 드는 문제였다.

 

dp[i][j]로 2차원 배열을 둔 후, i를 코딩력 , j를 알고력을 나타내게 하였다.

 

이어서 배열을 채워나갔는데 내가 문제를 해결한 과정은 아래와 같다.

 

 

1. 필요한 최대 알고력,코딩력 확인 (이하 알고력 => alp 코딩력 cop)

2. dp 크기를 maxCop , maxAlp 만큼 잡아서 만듬

3. 배열을 처음 초기화 할때 만들 수 있는 가장 최대의 값들로 초기화한다.

4. 배열을 순회할 때 alp,cop부터 순회한다 <= 내가 가진 알고력과 코딩력부터 시작해야함

 

 

이때 생각을 해보자. dp를 순회한다면 그냥 순회해도 될까? 정답은 ㅇ 이다.

결국 알고력이든 코딩력이든 -가 될 수는 없기에 문제를 풀던 자력으로 알고,코딩력을 올리던 결국 2차원 배열의 우하단 방향으로 값을 갱신해줄수 밖에 없기 때문이다.

 

두번째로 사용한 방법은 최대 알고력,최대 코딩력을 넘어갔을 경우이다.

 

최대 알고력과 최대 코딩력 둘중 하나가 넘어가도 계속 문제를 풀어야 하는 경우가 있다. 따라서 최대 알고력이 넘어가더라도 최대 알고력이라고 가정하고 dp를 채워나가면 된다.

 

5. dp의 마지막 항목을 조회하면 답이 나온다.

 

 

문제에 대한 접근방법 자체는 좋았는데 시간이 꽤나 오래걸린 문제였다..

 

초기값에 maxAlp와 maxCop를 0으로 두었었는데 이때문에 값이 이상하게 나오는 경우가 발생한 것. 항상 초기값을 잘 생각하고 두는 습관이 필요한 것 같다.

 

 

 

 

function solution(alp, cop, problems) {
    let maxAlp = alp
    let maxCop = cop
    
    for (const [alp_req,cop_req,alp_rwd,cop_rwd,cost] of problems){
        if (alp_req > maxAlp) maxAlp = alp_req
        if (cop_req > maxCop) maxCop = cop_req
    }
    
    const dp = [...Array(maxCop+1)].map((_,c) => [...Array(maxAlp+1)].map((__,a) => c+a-alp-cop))
    
    for (let i = cop ; i <= maxCop ; i++){
        for (let j = alp ; j <= maxAlp ; j++){
            
            for (const [alp_req,cop_req,alp_rwd,cop_rwd,cost] of problems){
                if(alp_req > j || cop_req > i) continue
                const nxCop = (i+cop_rwd)>maxCop ? maxCop : i+cop_rwd
                const nxAlp = (j+alp_rwd)>maxAlp ? maxAlp : j+alp_rwd
                if(dp[nxCop][nxAlp] > dp[i][j]+cost) dp[nxCop][nxAlp]  = dp[i][j]+cost
            }
        }
    }
    
    return dp[maxCop][maxAlp]
}