[lv3]코딩 테스트 공부 (자바스크립트)

https://school.programmers.co.kr/learn/courses/30/lessons/118668?language=javascript

프로그래머스

 

• 처음 생각해 본 경우의 수 
  1. 알고력 코딩력이 문제에서 요하는 알고 코딩력보다 크다면 풀어버리기
  2. 요하는 것보다 작다면 1시간 당 코딩 또는 알고력이 +1 이니까 (필요 코딩력 - 현재 코딩력),(필요 알고력-현재 알고력) 
  3. 풀었던 문제들에 대해 문제 돌면서 알고 코딩력 얻기 
• 위의 경우에서의 에러 사항은 문제를 풀어서 코딩/알고력을 얻다가 시간 당 1씩 얻는 경우도 있고, 시간당 얻다가 문제 풀어서 필요력을 취하는 경우가 있다는 것. 
• 따라서 필요력보다 작다면 1씩 플러스 해주거나 풀었던 것들에 대해 또 풀어보는 경우 모두 찾아야 함. 
• 이 때, 방문 했던 것들에 대해 continue를 해준다면 중복 처리 방지 가능
• problems의 길이가 최대 100이라 bfs를 돌린다면 되겠다고 생각했지만 효율 테스트에서 시간 초과에 걸림. 
• 탐색으로는 더 거를 순 없다는 생각에 dp를 생각해 봄. 
• 최대 시간을 알지 못하니 기준을 시간으론 잡을 순 없었음.
• 풀었던 문제들의 갯수를 기준으로 값에는 시간을 넣자니 예외 상황이 여럿 생김
• 따라서 알고력과 코딩력을 기준으로 2차원 dp 짬
• 현재의 알고력과 코딩력을 기준으로 해당 dp에는 문제를 풀었을 때의 최단 시간을 넣어줌
•  

function solution(alp, cop, problems) {
    let maxAlp = Math.max(alp, ...problems.map((p) => p[0]));
    let maxCop = Math.max(cop, ...problems.map((p) => p[1]));

    // DP 테이블 초기화 (최대 크기는 151x151)
    let dp = Array.from({ length: maxAlp + 1 }, () =>
        Array(maxCop + 1).fill(400)
    );
    dp[alp][cop] = 0;

    for (let i = alp; i <= maxAlp; i++) {
        for (let j = cop; j <= maxCop; j++) {
            if (i + 1 <= maxAlp) {	// 알고력 + 1
                dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
            }

            if (j + 1 <= maxCop) {	// 코딩력 +1
                dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
            }

            problems.forEach((p) => {
                const [a, c, aa, cc, t] = p;
                if (i >= a && j >= c) {	//풀 수 있는 문제들에 대해 얻을 수 있는 최단 시간을 dp에 넣어줌
                    const al = Math.min(maxAlp, i + aa);
                    const co = Math.min(maxCop, j + cc);
                    dp[al][co] = Math.min(dp[i][j] + t, dp[al][co]);
                }
            });
        }
    }

    return dp[maxAlp][maxCop];
}