반응형
📖 문제
💡 풀이 방식
• 그리디
1. 연속된 5개의 광물을 한 그룹으로 묶어 각각 다이아/철/돌 곡괭이로 캤을 경우의 피로도의 합을 그룹별로 저장한다.
2. 돌로 캤을 때 가장 피로도가 높은 순으로 내림차순 정렬한다.
3. 정렬 후, 다이아 - 철 - 돌 곡괭이 순으로 캐야 피로도를 최소화할 수 있다.
🔺 코드
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
63
64
|
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
int answer = 0;
int cnt = Math.min(minerals.length/5 +1, picks[0]+picks[1]+picks[2]); // 곡괭이 수
int[][] section = new int[cnt][3]; // 5개씩 묶었을 때 광물별 피로도 계산
int dp = 0, ip = 0, sp = 0; // 다이아몬드 피로도, 철 피로도, 피로도
int idx = 0;
for(int i = 0 ; i < minerals.length ; i += 5) { // 5개씩
if(i/5 == cnt) // 곡괭이 수가 광물을 5개씩 묶은 그룹 수보다 적은 경우 탈출
break;
for(int j = i ; j < i+5 ; j++) {
if(minerals[j].equals("diamond")) {
dp += 1;
ip += 5;
sp += 25;
}
else if(minerals[j].equals("iron")) {
dp += 1;
ip += 1;
sp += 5;
}
else {
dp += 1;
ip += 1;
sp += 1;
}
if(j == minerals.length-1) break;
}
section[i/5][0] = dp;
section[i/5][1] = ip;
section[i/5][2] = sp;
dp = ip = sp = 0;
}
// "돌"로 캤을 때 피로도가 높은 순서대로 내림차순 정렬
Arrays.sort(section, (o1, o2) -> o2[2] - o1[2]);
for(int i = 0 ; i < cnt ; i++) {
if(picks[0] != 0) { // 다이아몬드
answer += section[i][0];
picks[0]--;
}
else if(picks[1] != 0) { // 철
answer += section[i][1];
picks[1]--;
}
else if(picks[2] != 0) { // 돌
answer += section[i][2];
picks[2]--;
}
}
return answer;
}
}
|
cs |
➕ 다른 풀이 방식
백트래킹을 사용할 수도 있다고 한다.
1) 백트래킹으로 곡괭이들 조합을 구한다.
2) 곡괭이 조합으로 모든 경우의 cost를 구해 minCost를 구한다.
💦 어려웠던 점
- 처음 아이디어 : picks배열을 돌면서 minerals배열을 5개씩 끊어서 캐도록 생각했었다.
🧐 새로 알게 된 내용
다,,, 복습을 열심히 해야겄다!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
반응형
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Level2] 배달 (JAVA) (0) | 2024.03.24 |
---|---|
[프로그래머스/Level2] 혼자 놀기의 달인 (JAVA) (0) | 2024.03.19 |
[프로그래머스/Level1] 공원 산책 (JAVA) (0) | 2024.03.18 |
[프로그래머스/Level3] 거스름돈 (JAVA) (0) | 2024.03.16 |
[프로그래머스/Level2] 테이블 해시 함수 (JAVA) (0) | 2024.03.16 |