[Programmers] 172927번 - 광물 캐기 [Java][C++]
1. 아이디어
주어진 광물들을 앞에서부터 연속으로 캐야하며 하나의 곡괭이가 5개의 광물까지 캘 수 있다는 점에서 주어진 광물들을 앞에서부터 5개씩 그룹을 묶어주는 것으로 시작했다.
그룹핑 이후에는 백트래킹 또는 그리디를 활용하면 해결할 수 있는데 먼저 백트래킹의 경우 5개씩 묶은 광물 그룹에 대해 앞에서부터 순서대로 곡괭이를 배치해서 광물을 캤을 때 피로도를 배치별로 구해서 최솟값을 찾는 방식으로 접근했다. 곡괭이의 수가 최대 15개, 광물 그룹의 수는 최대 10개로 백트래킹으로도 충분히 빠르게 계산해낼 수 있다.
그리디의 경우 어떤 그룹이든 좋은 곡괭이로 캘수록 피로도가 작으므로 좋은 곡괭이부터 쓰게 되고, 그러면 실제로 쓰이는 곡괭이 묶음이 자동으로 정해진다. 곡괭이가 그룹보다 많으면 나쁜 곡괭이는 그냥 남는다. 결국 남는 문제는 이미 정해진 곡괭이들을 어느 그룹에 나눠주느냐다. 두 그룹의 곡괭이를 서로 바꿔보면 더 좋은 곡괭이를 받아야 하는 쪽은 나쁜 곡괭이로 밀렸을 때 손해가 더 큰 쪽이다. 그룹의 다이아, 철, 돌 개수를 각각 $d$, $i$, $s$ 라 하고 이 손해를 계산해보면 다이아 곡괭이 대신 철 곡괭이를 쓸 때 $4d$, 철 곡괭이 대신 돌 곡괭이를 쓸 때 $20d + 4i$, 다이아 곡괭이 대신 돌 곡괭이를 쓸 때 $24d + 4i$ 만큼 늘어난다. 세 경우 모두 $s$ 는 상쇄되어 사라지고 $d$ 의 계수가 $i$ 의 계수보다 훨씬 크다.
여기서 한 그룹의 광물이 최대 5개라는 점이 결정적이다. $i$ 는 아무리 커도 5이므로 다이아가 하나만 더 많아도 그 차이가 철 개수 차이를 항상 따라잡는다. 따라서 주어진 광물 그룹을 다이아가 많은 순, 다이아가 동일하면 철이 많은 순으로 정렬한 후 앞 그룹부터 다이아, 철, 돌 곡괭이를 배정해주면 최소 피로도로 광물 캐기가 된다. 만약 그룹 상한이 6이었다면 철 6개짜리 그룹의 손해 24가 다이아 1개짜리 그룹의 손해 20을 넘어서므로 이 정렬 기준은 성립하지 않는다.
이때 곡괭이가 모자라서 모든 광물을 캘 수 없는 경우가 있으므로 곡괭이가 모자라면 이후 광물은 그룹핑 하지 않는 방식을 적용했다.
2. 복잡도
1. 백트래킹
| 시간복잡도 | 공간복잡도 |
|---|---|
| $O(N + 3^{\min(G,K)})$ | $O(N)$ |
$N$ = 광물 개수, $G$ = 그룹 수 $\lceil N/5 \rceil$, $K$ = 곡괭이 총 개수
2. 그리디
| 시간복잡도 | 공간복잡도 |
|---|---|
| $O(N + K \log K)$ | $O(K)$ |
$N$ = 광물 개수, $K$ = 곡괭이 총 개수
3. 코드
1. 백트래킹 [Java][C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
static int ans = Integer.MAX_VALUE;
public int solution(int[] picks, String[] minerals) {
int[][] cost = new int[(minerals.length + 4) / 5][3];
for (int i = 0; i < minerals.length; i++) {
String mineral = minerals[i];
if (mineral.equals("diamond")) {
cost[i / 5][0] += 1;
cost[i / 5][1] += 5;
cost[i / 5][2] += 25;
} else if (mineral.equals("iron")) {
cost[i / 5][0] += 1;
cost[i / 5][1] += 1;
cost[i / 5][2] += 5;
} else {
cost[i / 5][0] += 1;
cost[i / 5][1] += 1;
cost[i / 5][2] += 1;
}
}
dfs(0, picks[0] + picks[1] + picks[2], 0, picks, cost);
return ans;
}
static void dfs(int idx, int maxLen, int sum, int[] picks, int[][] cost) {
if (idx == maxLen || idx == cost.length) {
ans = Math.min(ans, sum);
return;
}
if (picks[0] > 0) {
picks[0]--;
dfs(idx + 1, maxLen, sum + cost[idx][0], picks, cost);
picks[0]++;
}
if (picks[1] > 0) {
picks[1]--;
dfs(idx + 1, maxLen, sum + cost[idx][1], picks, cost);
picks[1]++;
}
if (picks[2] > 0) {
picks[2]--;
dfs(idx + 1, maxLen, sum + cost[idx][2], picks, cost);
picks[2]++;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <climits>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
int ans = INT_MAX;
static void dfs(int idx, int maxLen, int sum, vector<int>& picks, vector<tuple<int, int, int>>& v) {
if (idx == maxLen || idx == v.size()) {
ans = min(ans, sum);
return;
}
auto& [di, ir, st] = v[idx];
if (picks[0] > 0) {
picks[0]--;
dfs(idx + 1, maxLen, sum + di, picks, v);
picks[0]++;
}
if (picks[1] > 0) {
picks[1]--;
dfs(idx + 1, maxLen, sum + ir, picks, v);
picks[1]++;
}
if (picks[2] > 0) {
picks[2]--;
dfs(idx + 1, maxLen, sum + st, picks, v);
picks[2]++;
}
}
int solution(vector<int> picks, vector<string> minerals) {
vector<tuple<int, int, int>> v((minerals.size() + 4) / 5);
for (int i = 0; i < minerals.size(); i++) {
string mineral = minerals[i];
auto& [di, ir, st] = v[i / 5];
if (mineral == "diamond") {
di += 1;
ir += 5;
st += 25;
} else if (mineral == "iron") {
di += 1;
ir += 1;
st += 5;
} else {
di += 1;
ir += 1;
st += 1;
}
}
dfs(0, picks[0] + picks[1] + picks[2], 0, picks, v);
return ans;
}
2. 그리디 [Java][C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
int pickCnt = picks[0] + picks[1] + picks[2];
int[][] cnt = new int[pickCnt][3];
for (int i = 0; i < Math.min(minerals.length, pickCnt * 5); i++) {
String mineral = minerals[i];
if (mineral.equals("diamond")) {
cnt[i / 5][0]++;
} else if (mineral.equals("iron")) {
cnt[i / 5][1]++;
} else {
cnt[i / 5][2]++;
}
}
Arrays.sort(cnt, (o1, o2) -> {
if (o1[0] != o2[0]) return Integer.compare(o2[0], o1[0]);
return Integer.compare(o2[1], o1[1]);
});
int ans = 0;
for (int[] arr : cnt) {
if (picks[0] > 0) {
ans += arr[0] + arr[1] + arr[2];
picks[0]--;
} else if (picks[1] > 0) {
ans += arr[0] * 5 + arr[1] + arr[2];
picks[1]--;
} else if (picks[2] > 0) {
ans += arr[0] * 25 + arr[1] * 5 + arr[2];
picks[2]--;
} else {
break;
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
int solution(vector<int> picks, vector<string> minerals) {
int pickCnt = picks[0] + picks[1] + picks[2];
vector<tuple<int, int, int>> v(pickCnt);
for (int i = 0; i < min((int)minerals.size(), pickCnt * 5); i++) {
string mineral = minerals[i];
auto& [di, ir, st] = v[i / 5];
if (mineral == "diamond") {
di++;
} else if (mineral == "iron") {
ir++;
} else {
st++;
}
}
sort(v.rbegin(), v.rend());
int ans = 0;
for (auto& [di, ir, st] : v) {
if (picks[0] > 0) {
ans += di + ir + st;
picks[0]--;
} else if (picks[1] > 0) {
ans += di * 5 + ir + st;
picks[1]--;
} else if (picks[2] > 0) {
ans += di * 25 + ir * 5 + st;
picks[2]--;
} else {
break;
}
}
return ans;
}