[프로그래머스] 코딩테스트 연습 with JS

알고리즘 스프린트 11일차 - [프로그래머스] Lv 3. 코딩테스트 연습

 

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

소요시간

2시간..

계획

이것 저것 생각하다가 겨우 DP로 풀었다..

접근법을 조금 일찍 떠올렸더라면, 더 빨리 풀 수 있었을텐데 조금 아쉽다.

히든 케이스가 있어서 거기서도 조금 애를 먹었다.

풀이

• dp[i][j] 로 알고력이 i, 코딩력이 j가 되기까지 걸리는 시간을 적을 것이다.
• now_alp, now_cop 가 현재 알고력과 코딩력이라 생각하고
• next_alp, next_cop는 문제를 풀었을 때 달성하는 알고력과 코딩력이다
• cost는 문제를 풀면서 소요되는 시간이다.
• 그렇다면 점화식은?
  • dp[next_alp][next_cop] = Math.min(dp[next_alp][next_cop], dp[now_alp, now_cop] + cost)
  • 최소 값으로 갱신해주면서 풀어준다
• now_alp와 now_cop는 처음에 매개변수로 주는 alp와 cop에서 시작해서 최대 값까지 반복한다
• 이때 최대값이란 모든 문제를 풀 수 있는 최소 알고력과 최소 코딩력이다.
• 나는 문제리스트에 알고력과 코딩력을 1씩 올려주는 방법도 문제로 넣어주었다
  • [0,0,1,0,1], [0,0,0,1,1] 이 두 개를 problems에 추가해주고 시작했다는 뜻
• 히든 케이스가 있는데, 처음에 주는 alp와 cop가 이미 모든 문제를 풀수있는 능력치인 경우다
  • 이 때는 그냥 alp와 cop를 최대값으로 변경해서 반복이 돌지 않도록 했다.

결과

코드

function solution(alp, cop, problems) {
    var goal_alp = 0;
    var goal_cop = 0;
    var totalProblems = [];
    
    for(let p = 0; p < problems.length; p++){
        totalProblems.push(problems[p]);
        goal_alp = Math.max(goal_alp, problems[p][0])
        goal_cop = Math.max(goal_cop, problems[p][1])
    }
    
    totalProblems.push([0,0,1,0,1]);
    totalProblems.push([0,0,0,1,1]);
    
    if(alp > goal_alp){
        alp = goal_alp;
    }
    if(cop > goal_cop){
        cop = goal_cop;
    }
    
    let dp = [];
    
    for(let i = 0; i <= goal_cop; i++){
        let temp = [];
        for(let j = 0; j <= goal_alp; j++){
            temp.push(151);
        }
        dp.push(temp);
    }
    
    dp[cop][alp] = 0;
    
    for(let i = cop; i <= goal_cop; i++){
        for(let j = alp; j <= goal_alp; j++){
            for(let p = 0; p < totalProblems.length; p++){
                if(i >= totalProblems[p][1] && j >= totalProblems[p][0]){
                    let next_alp = j+totalProblems[p][2];
                    let next_cop = i+totalProblems[p][3];
                    if(next_alp > goal_alp){
                        next_alp = goal_alp;
                    }
                    if(next_cop > goal_cop){
                        next_cop = goal_cop;
                    }
                    dp[next_cop][next_alp] = Math.min(dp[i][j] + totalProblems[p][4], dp[next_cop][next_alp])
                }
            }
        }
    }
    answer = dp[goal_cop][goal_alp];
    return answer;
}

마치며

좋아하는 DP문제가 나와도 접근을 빨리 못하니까 억울한 상황이 생긴다. 실전에서도 이러면 안된다. 빨리 많은 문제를 풀면서 접근법을 어느 정도 공식화 시켜야할 것 같다.