프로그래머스[JS] > 완전범죄

🧩문제링크

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

프로그래머스

🧩문제풀이

➕dfs로 접근 -> 실패 ( 시간초과 )

dfs로 푼 문제풀이다. 하지만 시간초과가 났다.

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

    dp[0][0] = 0;

    for (let r = 1; r <= info.length; r++) {
        let [aScore, bScore] = info[r - 1];
        for (let c = 0; c < m; c++) {
            dp[r][c] = Math.min(dp[r - 1][c] + aScore, dp[r][c]);

            if (c + bScore < m) {
                dp[r][c + bScore] = Math.min(dp[r - 1][c], dp[r][c + bScore]);
            }
        }
    }
    let min = Infinity;

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

    return min === Infinity ? -1 : min;
}

➕dp로 접근 -> 성공

2차원 배열을 만들어 순서대로 값을 채우면 된다. 값을 채울때는 점화식을 이용해서 채우고 값을 채운 2차원배열에서 마지막 행의 값들 중에 n미만이면서 가장 작은 값을 return 하면 문제를 풀 수 있다. 

2차원배열은 아래와 같은 방식으로 설계했다. 이해를 돕기위해 문제에서 주어진 Test case를 적용하여 2차원 배열을 만들어 보았다. ( info = [[1,2],[2,3],[2,1]], n=4, m=4 )

 

위와 같은 2차원 배열을 이용하면 b의 흔적갯수가 m을 넘어가는 경우는 생기지 않기 때문에 결국 a조건만을 고려하면 된다.

2차원 배열 설계는 위와 같이 진행하고 점화식은 아래와 같다.

• 아래에서 말하는 `aScore`, `bScore`는 각각 info[r-1]를 a가 훔쳤을때 흔적갯수, b가 훔쳤을때 흔적갯수를 의미한다. 
• dp[r-1][c] 에서 a 를 선택했을 때 => dp[r][c] = Math.min(dp[r][c-1] + aScore, dp[r][c] )
• dp[r-1][c] 에서 b 를 선택했을 때 => dp[r][c+bScore] = Math.min(dp[r-1][c], dp[r][c+bScore] )

2차원배열과 점화식을 고려하여 아래와 같이 코드를 구현할 수 있었다.

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

    dp[0][0] = 0;

    for (let r = 1; r <= info.length; r++) {
        let [aScore, bScore] = info[r - 1];
        for (let c = 0; c < m; c++) {
            dp[r][c] = Math.min(dp[r - 1][c] + aScore, dp[r][c]);

            if (c + bScore < m) {
                dp[r][c + bScore] = Math.min(dp[r - 1][c], dp[r][c + bScore]);
            }
        }
    }
    let min = Infinity;

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

    return min === Infinity ? -1 : min;
}