[프로그래머스] 완전범죄 - JavaScript

문제 출처

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

프로그래머스

문제 설명

A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

물건을 훔칠 때 조건은 아래와 같습니다.

• 물건 i를 훔칠 때,
  • A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
  • B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
• 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.

경찰에 붙잡히는 조건은 아래와 같습니다.

• A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
• B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.

각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.

---

제한사항

• 1 ≤ info의 길이 ≤ 40
  • info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태입니다.
  • 1 ≤ 흔적 개수 ≤ 3
• 1 ≤ n ≤ 120
• 1 ≤ m ≤ 120

---

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예 설명

입출력 예 #1

첫 번째와 세 번째 물건을 B도둑이 훔치고 두 번째 물건을 A도둑이 훔치면, A도둑에 대한 흔적은 총 2개이고 B도둑에 대한 흔적은 총 3개입니다. 목표를 달성하면서 A도둑에 대한 흔적 개수를 2보다 더 낮게 만들 수 없습니다.
따라서 2를 return 해야 합니다.

입출력 예 #2

B도둑이 모든 물건을 훔쳐도 B의 흔적이 7개 이상 쌓이지 않습니다.
따라서 A도둑의 흔적은 최소 0이 되며, 0을 return 해야 합니다.

입출력 예 #3

B도둑이 한 번이라도 물건을 훔치면 B의 흔적이 최소 1개 이상 남습니다. 따라서 모든 물건을 A도둑이 훔쳐야 하며, 이 경우에도 A의 흔적은 7개 미만입니다.
따라서, A도둑이 모든 물건을 훔칠 때의 흔적 개수 6을 return 해야 합니다.

입출력 예 #4

어떤 방법으로도 두 도둑 모두 경찰에 붙잡히지 않고 모든 물건을 훔칠 수 없습니다.
따라서 -1을 return 해야 합니다.

풀이 방법

• DP를 활용하는 문제였다.
  • 2차원 배열 prev와 cur을 활용하여, a가 x ( x <= n) 를 훔치고, b가 y ( y <= m )를 훔쳤을 때 그때의 A흔적의 최소량을 저장한다.
  • DP저장만 하면 이외는 반복문만 수행하면 되기에 괜찮은 문제였다.
• A가 저장하는 경우와 B가 저장하는 경우 모두 cur에 저장하고, 이후 prev 배열로 복사함으로써 지속적인 신규 생성을 방지한다.

풀이 코드

function solution(info, n, m) {
    const N = info.length;
    const min = Number.MAX_SAFE_INTEGER;

    //a가 x를 훔치고 b가 y를 훔쳤을 때, 그때의 A 최소흔적을 저장하는 배열
    let prev = Array.from({length: n + 1}, () => Array(m + 1).fill(min));
    let cur = Array.from({length: n + 1}, () => Array(m + 1).fill(min));
    
    prev[0][0] = 0;
    
    for(let i = 0; i < N; i++){
        const [aItem, bItem] = info[i];
        
        for(let j = 0; j <= n; j++){
            cur[j].fill(min);
        }
        
        for(let a = 0; a < n; a++){
            for(let b = 0; b < m; b++){
                if(prev[a][b] === min) continue;
                
                //A가 훔치는 경우~
                let newA = Math.min(n, a + aItem);
                cur[newA][b] = Math.min(cur[newA][b], prev[a][b] + aItem);
                //B가 훔치는 경우~
                let newB = Math.min(m, b + bItem);
                cur[a][newB] = Math.min(cur[a][newB], prev[a][b] );
            }
        }
        //스왑
        [prev, cur] = [cur, prev];
    }
    
    let result = min;   
    for(let a = 0; a < n; a++){
        for(let b = 0; b < m; b++){
            if(prev[a][b] !== min){
                result = Math.min(result, prev[a][b]);                       }
        }
    }
    return result === min ? -1 : result;
}

결과

회고

• DP만은 진짜어렵다