프로그래머스 [Lv. 3] 코딩 테스트 공부 {언어 : JavaScript} [다시 풀어 보기] [시간 초과 해결]

문제 링크

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

프로그래머스

정답 코드

function solution(alp, cop, problems) {
    let [alp_goal, cop_goal] = [0, 0];
    for (const [alp_req, cop_req, alp_rwd, cop_rwd, cost] of problems) {
        alp_goal = Math.max(alp_goal, alp_req);
        cop_goal = Math.max(cop_goal, cop_req);
    }

    alp = Math.min(alp, alp_goal);
    cop = Math.min(cop, cop_goal);

    const INF = 10 ** 10;
    let dp = Array.from({length: alp_goal + 1}, () => Array(cop_goal + 1).fill(INF));
    dp[alp][cop] = 0;

    for (let a = alp; a <= alp_goal; a++) {
        for (let c = cop; c <= cop_goal; c++) {
            // 1. 코딩력 또는 알고력 1 올리는 경우
            if (a < alp_goal) dp[a + 1][c] = Math.min(dp[a + 1][c], dp[a][c] + 1);
            if (c < cop_goal) dp[a][c + 1] = Math.min(dp[a][c + 1], dp[a][c] + 1);

            // 2. 문제를 풀어서 올리는 경우
            for (const [alp_req, cop_req, alp_rwd, cop_rwd, cost] of problems) {
                if (a >= alp_req && c >= cop_req) {
                    const new_alp = Math.min(a + alp_rwd, alp_goal);
                    const new_cop = Math.min(c + cop_rwd, cop_goal);
                    dp[new_alp][new_cop] = Math.min(dp[new_alp][new_cop], dp[a][c] + cost);
                }
            }
        }
    }

    return dp[alp_goal][cop_goal];
}

풀이 방법

1. 목표 설정: 주어진 문제 중 가장 높은 alp_req와 cop_req를 찾아서 alp_goal과 cop_goal로 설정
2. 초기 상태 설정: 현재 알고력과 코딩력이 목표치보다 높으면, 그 이상의 값은 필요하지 않으므로 목표치로 제한한다.
   • 범위를 줄여서 최적화를 했다고 본다.
3. DP 테이블 초기화: dp[a][c]는 알고력 a와 코딩력 c에 도달하기 위한 최소 시간을 저장한다. 초기에는 모든 값을 무한대로 설정하고, 시작점인 (alp, cop)에서의 시간은 0으로 설정한다.
4. DP 테이블 갱신: 알고력과 코딩력을 1씩 올리는 경우와 문제를 풀어서 보상을 받는 경우를 고려하여, 각각의 상태에 도달하기 위한 최소 시간을 DP 테이블에 갱신다.
5. 결과 반환: 목표 알고력(alp_goal)과 코딩력(cop_goal)에 도달하기 위한 최소 시간을 반환

느낀점

• dp의 크기를 단순하게 (alp_goal + 2) * (cop_goal + 2)로 각각 1씩만 더 해줬을 뿐인데 시간 초과가 났다.
• 시간초과가 발생한 이유
  • alp_goal의 최대값 = 150
  • cop_goal의 최대값 = 150
  • problems의 최대 길이 = 100
  • (alp_goal + 1) * (cop_goal + 1) * problems.length = 2,280,100
  • (alp_goal + 2) * (cop_goal + 2) * problems.length = 2,310,400
  • 30000정도의 연산이 늘어나게 된다.
• 큰 차이가 아니라고 생각했지만 앞으로 배열의 크기를 늘리는 것에는 신중해야 겠다고 느꼈다.