[programmers/js] 코딩 테스트 공부

코딩 테스트 공부

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

문제 설명

알고력(alp)과 코딩력(cop)이라는 두 능력을 가지고 있습니다.

여러 개의 문제(problems)가 주어지며, 각 문제는 다음과 같은 정보를 가집니다.

alp_req: 문제를 풀기 위한 최소 알고력
cop_req: 문제를 풀기 위한 최소 코딩력
alp_rwd: 문제를 풀면 얻는 알고력
cop_rwd: 문제를 풀면 얻는 코딩력
cost: 문제를 푸는 데 걸리는 시간

alp와 cop를 각각 1씩 올리는 공부도 가능하며, 각각 1의 시간이 소요됩니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

풀이

1. 목표 능력 설정
모든 문제 중 가장 큰 alp_req, cop_req를 목표치로 설정한다.

const maxAlp = Math.max(...problems.map(p => p[0]));
const maxCop = Math.max(...problems.map(p => p[1]));

2. 초기 능력 제한
이미 목표 능력 이상이라면, 더 계산할 필요 없도록 제한

alp = Math.min(alp, maxAlp);
cop = Math.min(cop, maxCop);

3. DP 테이블 정의
dp[i][j] = i의 알고력과 j의 코딩력을 얻기까지의 최소 시간

모든 값은 Infinity로 초기화하고, 시작 지점은 0으로 설정

const dp = Array.from({ length: maxAlp + 2 }, () => Array(maxCop + 2).fill(Infinity));
dp[alp][cop] = 0;

4. 상태 전이
1) 공부로 능력 1씩 올리기

dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);

2) 문제 풀기
현재 능력으로 풀 수 있는 문제만 고려

for (const [alp_req, cop_req, alp_rwd, cop_rwd, cost] of problems) {
    if (i >= alp_req && j >= cop_req) {
        const ni = Math.min(maxAlp, i + alp_rwd);
        const nj = Math.min(maxCop, j + cop_rwd);
        dp[ni][nj] = Math.min(dp[ni][nj], dp[i][j] + cost);
    }
}

5. 정답 반환
목표 알고력/코딩력 상태에 도달하는 최소 시간을 반환

return dp[maxAlp][maxCop];

전체 코드

function solution(alp, cop, problems) {
    // 우리의 최종 목표
    const maxAlp = Math.max(...problems.map(p => p[0]));
    const maxCop = Math.max(...problems.map(p => p[1]));
    
    // 최소 범위로 자르기,
    alp = alp > maxAlp ? maxAlp : alp; // Math.min(alp, maxAlp);
    cop = cop > maxCop ? maxCop : cop;
    
    const dp = Array.from({ length: maxAlp + 2 }, () => Array(maxCop + 2).fill(Infinity));
    dp[alp][cop] = 0;

    for (let i = alp; i <= maxAlp; i++) {
        for (let j = cop; j <= maxCop; j++) {
            // 공부로 하나 올리는 경우
            dp[i + 1][j] = dp[i + 1][j] > dp[i][j] + 1 ? dp[i][j] + 1 : dp[i + 1][j];
            dp[i][j + 1] = dp[i][j + 1] > dp[i][j] + 1 ? dp[i][j] + 1 : dp[i][j + 1]; 

            for (const [alp_req, cop_req, alp_rwd, cop_rwd, cost] of problems) {
                if (i >= alp_req && j >= cop_req) {
                    const ni = maxAlp > i + alp_rwd ? i + alp_rwd : maxAlp;
                    const nj = maxCop > j + cop_rwd ? j + cop_rwd : maxCop;
                    dp[ni][nj] = Math.min(dp[ni][nj], dp[i][j] + cost);
                }
            }
        }
    }

    return dp[maxAlp][maxCop];
}