[JavaScript] 2025 프로그래머스 코드챌린지 2차 예선 - 완전범죄

Q. 문제

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. minA를 n으로 초기화하여 모든 탐색이 끝난 후에도 n이면 -1로 return

2. DFS 사용하여 각 노드별로 가능한 경우의 수를 모두 탐색하여 제일 적은 aSum을 return

=> 시간초과 발생, info.length === 40일 경우 2^40의 시간복잡도를 갖게 됨

3. memo를 만들어 방문한 노드는 다시 방문하지 않도록 함

4. info 마지막 인덱스에 도착했을 때 minA와 aSum을 비교하여 더 적은 수를 minA에 저장

5. 4를 반복하며 최적의 경로를 찾아냄

 

A. 풀이(첫시도: 시간초과)

function solution(info, n, m) {
    let minA = n;

    function dfs(index, aSum, bSum) {
        if (index === info.length) {
            if (aSum < n && bSum < m) {
                minA = Math.min(minA, aSum);
            }
            return;
        }

        if (aSum >= n || bSum >= m) {
            return -1;
        }
        
        dfs(index + 1, aSum + info[index][0], bSum);

        dfs(index + 1, aSum, bSum + info[index][1]);
    }

    dfs(0, 0, 0)
    
    if(minA != n) {
        return minA
    } else {
        return -1
    }
}

 

A. 풀이(memo 추가)

function solution(info, n, m) {
    let minA = n; //가질 수 없는 minA값으로 초기화
    const memo = new Set(); //memo Set 생성

    //dfs로 탐색
    function dfs(index, aSum, bSum) {
        //탐색 노드를 key로 저장 후 memo
        const key = `${index},${aSum},${bSum}`;
        if (memo.has(key)) return;
        memo.add(key);

        //조건을 만족할 수 없는 info일 경우 return 
        if (aSum >= n || bSum >= m) return;

        //조건을 만족하며 마지막 노드에 방문했을 때 minA와 현재 aSum 중 최소값 return
        if (index === info.length) {
            if (aSum < n && bSum < m) {
                minA = Math.min(minA, aSum);
            }
            return;
        }

        //A 선택
        dfs(index + 1, aSum + info[index][0], bSum);
        //B 선택
        dfs(index + 1, aSum, bSum + info[index][1]);
    }

    dfs(0, 0, 0);

    return minA === n ? -1 : minA;
}