A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.
물건을 훔칠 때 조건은 아래와 같습니다.
info[i][0]
개의 A에 대한 흔적을 남깁니다.info[i][1]
개의 B에 대한 흔적을 남깁니다.경찰에 붙잡히는 조건은 아래와 같습니다.
n
개 이상이면 경찰에 붙잡힙니다.m
개 이상이면 경찰에 붙잡힙니다.각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info
, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n
, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m
이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.
info
의 길이 ≤ 40info[i]
는 물건 i
를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수
, B에 대한 흔적 개수
]의 형태입니다.흔적 개수
≤ 3n
≤ 120m
≤ 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들을 아래 정렬 기준에 따라 정렬한다.
info[i][0]
)이 큰 것부터 작은 순서대로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가 물건을 훔치게 한다면,
할 수 있다.
다만 위의 풀이는 아래와 같은 문제가 있다.
m
보다 작다면, 그 빈 공간을 활용하는 것이 더 나은 해가 될 가능성이 있기 때문이다.완전탐색을 하여 모든 경우를 살펴본다고 하더라도, 최대 번의 연산을 해야 하므로 비효율적이다 (물건을 훔칠 사람의 경우의 수 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가지가 있다.
이 두 가지 경우를 모두 고려하여 메모이제이션 배열에 반영하면 되고, 코드 상에서 이를 표현한 점화식은 아래와 같다. 이해를 돕기 위해 예외처리를 위한 코드는 제거하였다.
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()
)만을 저장한다.
memo[i][j]
)이 늘어나게 한다. 이때 늘어나는 양은 현재 물건의 A에 대한 흔적 값(info[i][0]
)이다. B의 누적 흔적 값(memo
배열의 열)에는 변화가 없다.memo[i][j]
)에는 변함이 없다. 다만, 이전 값에 비해 B의 누적 흔적 값(memo
배열의 열)이 늘어나게 한다. 이때 늘어나는 양은 현재 물건의 B에 대한 흔적 값(info[i][1]
)이다.즉, A가 물건을 훔치는 경우에는 배열 자체에 저장되는 값을 늘리고, B가 물건을 훔치는 경우에는 배열의 열 값을 늘린다. 두 경우를 모두 체크하여 메모이제이션 배열을 업데이트한다.
모든 업데이트를 마친 후, 마지막 행의 배열요소 중 가장 작은 값이 최적해이다.