[programmers/js] 완전범죄

완전범죄

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. 완전 탐색 + 백트래킹 (시간 초과)
   완전 탐색을 진행하며 A, B 도둑의 점수를 확인하며 가지치기를 진행합니다.

function solution(info, n, m) {
    let minA = Infinity;
    
    function dfs(index, traceA, traceB) {
        if (traceA >= n || traceB >= m) return;

      	if (index === info.length) {
            minA = Math.min(minA, traceA);
            return;
        }
        
        dfs(index + 1, traceA + info[index][0], traceB);
        dfs(index + 1, traceA, traceB + info[index][1]);
    }
    
    dfs(0, 0, 0);
    
    return minA === Infinity ? -1 : minA;
}

2. 메모이제이션 + 백트래킹

function solution(info, n, m) {
    const dp = new Map(); // 메모이제이션을 위한 Map
    let minA = Infinity;
    
    function dfs(index, traceA, traceB) {
        if (traceA >= n || traceB >= m) return Infinity;
        if (index === info.length) return traceA;
        
        const key = `${index},${traceA},${traceB}`;
        if (dp.has(key)) return dp.get(key);
        
        const pickA = dfs(index + 1, traceA + info[index][0], traceB);
        const pickB = dfs(index + 1, traceA, traceB + info[index][1]);
        const result = Math.min(pickA, pickB);
      
        dp.set(key, result);
        return result;
    }
    
    const answer = dfs(0, 0, 0);
    return answer === Infinity ? -1 : answer;
}