(Java) 프로그래머스 완전범죄

프로그래머스 완전범죄 문제 링크

문제 설명

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	15%	info[i][1] = 1
#2	40%	info의 길이 ≤ 20
#3	45%	추가 제한 사항 없음

---

입출력 예

info	n	m	result
[[1, 2], [2, 3], [2, 1]]	4	4	2
[[1, 2], [2, 3], [2, 1]]	1	7	0
[[3, 3], [3, 3]]	7	1	6
[[3, 3], [3, 3]]	6	1	-1

---

입출력 예 설명

입출력 예 #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 해야 합니다.

---

답안

class Solution {
    public int solution(int[][] info, int n, int m) {
        int[][] memo = new int[info.length][m];
        int INF = 120;
        for (int i = 0; i < info.length; i++) {
            for (int j = 0; j < m; j++) {
                memo[i][j] = INF;
            }
        }
        memo[0][0] = info[0][0];
        if (info[0][1] < m) {
            memo[0][info[0][1]] = 0;
        }
        
        if (info.length == 1) {
            return info[0][1] < m ? 0 : info[0][0];
        }
        
        for (int i = 1; i < info.length; i++) {
            for (int j = 0; j < m; j++) {
                memo[i][j] = Math.min(memo[i][j], memo[i-1][j] + info[i][0]);
                if (j + info[i][1] < m) {
                    memo[i][j+info[i][1]] = Math.min(memo[i][j+info[i][1]], memo[i-1][j]);
                }
            }
        }
        
        int answer = INF;
        for (int j = 0; j < m; j++) {
           answer = Math.min(answer, memo[info.length-1][j]);
        }
        
        return (answer < n) ? answer : -1;
    }
}

풀이

요약: 그리디로 풀려고 했으나 DP로 문제를 해결하였다. 세부적인 설명을 듣고 싶다면 아래를 참고하고, 그렇지 않다면 스킵하자.

필자는 이 문제를 처음 보았을 때, 그리디로 해결 가능하지 않을까 생각했다. 그래서 아래와 같은 코드를 작성했다.

import java.util.*;

class Solution {
    public int solution(int[][] info, int n, int m) {
        Arrays.sort(info, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(b[0], a[0]);
            }
            return Integer.compare(a[1], b[1]);
        });
        
        int aSum = 0;
        int bSum = 0;
        for (int i = 0; i < info.length; i++) {
            if (bSum + info[i][1] < m) {
                bSum += info[i][1];
                continue;
            }
            if (aSum + info[i][0] < n) {
                aSum += info[i][0];
                continue;
            }
            return -1;
        }
        
        int answer = aSum;
        return answer;
    }
}

위 코드에 대한 설명은 다음과 같다.

info 배열의 row들을 아래 정렬 기준에 따라 정렬한다.

• A에 대한 흔적 값(info[i][0])이 큰 것부터 작은 순서대로
• A에 대한 흔적 값(info[i][0])이 같다면, B에 대한 흔적 값(info[i][1])이 작은 것부터 큰 순서대로

info	n	m
[[1, 2], [2, 3], [2, 1]]	4	4

즉, 위와 같은 입력 예에서는 info 배열이 아래와 같이 정렬된다.

2	1
2	3
1	2

이렇게 정렬한 뒤 배열의 앞에서부터 최대한 B가 물건을 훔치게 한다면,

• A의 부담을 최대한 줄이면서 (A의 흔적 값이 큰 물건을 B에게 떠넘김)
• 그와 동시에 B가 최대한 많은 물건을 훔치도록 (A의 부담이 같다면 B의 부담이 적은 물건을 훔침)

할 수 있다.

다만 위의 풀이는 아래와 같은 문제가 있다.

• 항상 최적이 아니다. B가 훔칠 물건을 모두 정한 후에, B의 누적 흔적 값이 m보다 작다면, 그 빈 공간을 활용하는 것이 더 나은 해가 될 가능성이 있기 때문이다.
  
• 훔치지 못한다고 판단하여 -1을 반환하더라도 실제로는 훔치는 것이 가능한 경우가 있다. 해가 존재하더라도, 알고리즘에서 도출한 greedy한 해는 A의 부담을 줄이는 방향만 고려하기 때문에 범위를 넘어설 수 있다.
  

완전탐색을 하여 모든 경우를 살펴본다고 하더라도, 최대 $2^{40}$번의 연산을 해야 하므로 비효율적이다 (물건을 훔칠 사람의 경우의 수 2 ^ 물건의 개수 40).

따라서, 이전의 결과를 활용해 최적해를 찾는 DP를 사용하는 것이 유리하다.

이전의 결과(물건이 1개일 때, 2개일 때, …, info.length-1개일 때의 최소 누적 흔적 값)를 이용해, 현재의 결과(물건이 2개일 때, 3개일 때, … info.length개일 때의 A의 최소 누적 흔적 값)을 업데이트하는 과정을 반복하면 될 것이다.

다만, 이때 knapsack 문제와 유사하게 B의 누적 흔적 값(knapsack의 가방 크기)을 고려해야 한다.

그러므로 '물건이 i개일 때'를 표현하는 차원 1개와, 그때의 B의 누적 흔적 값을 표현하는 차원 1개 총 2차원 메모이제이션 배열이 필요하다.

이러한 info.length * m 크기의 배열에서 모든 배열요소를 순서대로(행의 오름차순, 같은 행 내에서는 열의 오름차순으로) 업데이트하면, 마지막 행(모든 물건을 고려했을 때의 A의 누적 흔적 값의 최소값) 중 가장 작은 값을 최적해라고 할 수 있다.

배열요소를 업데이트할 때, 할 수 있는 행동은 2가지가 있다.

• 해당 물건(i번째 물건)을 A가 훔치게 한다.
  • 이때, A의 누적 흔적 값은 늘어나고 B의 누적 흔적 값은 변함없다.
• 해당 물건(i번째 물건)을 B가 훔치게 한다.
  • 이때, A의 누적 흔적 값은 변함없지만, B의 누적 흔적 값이 늘어난다.

이 두 가지 경우를 모두 고려하여 메모이제이션 배열에 반영하면 되고, 코드 상에서 이를 표현한 점화식은 아래와 같다. 이해를 돕기 위해 예외처리를 위한 코드는 제거하였다.

memo[i][j] = Math.min(memo[i][j], memo[i-1][j] + info[i][0]);  // A가 훔치는 경우
memo[i][j+info[i][1]] = Math.min(memo[i][j+info[i][1]], memo[i-1][j]);  // B가 훔치는 경우

두 경우 모두 이전 값(memo[i-1][j])을 활용하여, 최적의 값(Math.min())만을 저장한다.

• A가 물건을 훔치는 경우에는 이전 값에 비해 현재 A의 누적 흔적 값(memo[i][j])이 늘어나게 한다. 이때 늘어나는 양은 현재 물건의 A에 대한 흔적 값(info[i][0])이다. B의 누적 흔적 값(memo 배열의 열)에는 변화가 없다.
• B가 물건을 훔치는 경우에는 현재 A의 누적 흔적 값(memo[i][j])에는 변함이 없다. 다만, 이전 값에 비해 B의 누적 흔적 값(memo 배열의 열)이 늘어나게 한다. 이때 늘어나는 양은 현재 물건의 B에 대한 흔적 값(info[i][1])이다.

즉, A가 물건을 훔치는 경우에는 배열 자체에 저장되는 값을 늘리고, B가 물건을 훔치는 경우에는 배열의 열 값을 늘린다. 두 경우를 모두 체크하여 메모이제이션 배열을 업데이트한다.

모든 업데이트를 마친 후, 마지막 행의 배열요소 중 가장 작은 값이 최적해이다.