2025-03-31 TIL

코딩테스트 문제 풀이

코딩테스트를 잠깐 안 풀었다고 또 문제가 헷갈린다. 이번에는 DP 관련 문제를 풀었다.

function solution(info, n, m) {
    let dp = Array.from({ length: info.length + 1 }, () => {
        return Array(m).fill(Infinity);
    });

    dp[0][0] = 0;

    for (let i = 1; i <= info.length; i++) {
        let [a_score, b_score] = info[i - 1];
        for (let c = 0; c < m; c++) {
            dp[i][c] = Math.min(dp[i - 1][c] + a_score, dp[i][c]);


            if (c + b_score < m) {
                dp[i][c + b_score] = Math.min(dp[i - 1][c], dp[i][c]);
            }
        }
    }

    let minValue = Infinity;

    dp[info.length].forEach((v) => {
        if (v < n) {
            minValue = Math.min(minValue, v);
        }
    })

    return minValue !== Infinity ? minValue : -1;
}

//이거 동적 기획법 문제니까 헷갈리면 다시 보도록 하자.
//그러니까 모든 경우의 수에 맞는 칸을 집어 넣어 준다고 생각해 보자.
//공간 효율성은 좀 떨어지는 방법일 수 있다.