[JS] 프로그래머스 완전 탐색

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

프로그래머스

 

전형적인 0-1 배낭 문제

배낭의 무게 + 1만큼 배열의 길이를 선언한 뒤에

물건을 모두 넣으면서 배열을 갱신해 나간다.

 

-> 완전 탐색으로 변형하자면

배낭의 무게 = A의 최댓값 n - 1 (n 이상이면 안되므로)

=> 배열의 길이 n 선언

훔치는 물건 info를 순회하면서 배열을 갱신해 나간다.

 

사실 이 문제를 3번 풀었는데

1. 2차원 배열

2. 1차원 배열, 새로운 배열 갱신 (이전 배열, 갱신된 배열 바꿔치기 반복)

3. 1차원 배열, 역순(이전 값 오염 방지)

 

현재 코드는 3번 코드이다.

따라서 b가 훔치는 경우 Math.min(prevB + b, dp[j]) 가 아닌 prevB + b를 해주고

prevB + b가 m 이상인 경우 Infinity로 없애버린다.

 

역순에 대한 설명은 주석에 나와 있다.

function solution(info, n, m) {
    const len = info.length;
    
    let dp = Array(n).fill(Infinity);
    
    dp[0] = 0
    
    // info를 모두 순회해야 하므로
    for (let i = 0; i < len; i++) {
        const [a, b] = info[i];
        
        // dp 배열을 순회하면서 이전 값을 갱신
        // 역순 + a가 먼저 훔치고 b가 훔치는 경우 갱신
        // 이유 : dp[j]의 오염 때문 
        // (b가 이미 훔친 상황에서 a가 훔칠 수 있음)
        for (let j = n - 1; j >= 0; j--) {
            // 이전 것이 없다 -> 없다.
            if (dp[j] === Infinity) continue;
            
            const prevB = dp[j];
            
            // a가 훔치는 경우
            if (j + a < n) {
                dp[j + a] = Math.min(prevB, dp[j + a]);
            }
            
            // b가 훔치는 경우
            if (prevB + b < m) {
                dp[j] = prevB + b;
            } else {
                dp[j] = Infinity;
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (dp[i] < m) {
            return i;
        }
    }
    
    return -1;
}