알고리즘 문제풀이
[Programmers] 프로그래머스 Lv.2 광물 캐기 문제풀이(C++)
도리컴
2023. 5. 12. 22:55
반응형
재귀를 이용해서 모든 경우의 수를 탐색하는 문제 / 아이디어는 쉬웠으나 구현하는 동안 등호표시, 배열 요소 삭제 깜빡하는 것 등 사소한 실수가 잦았던 문제였음
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#include <string>
#include <vector>
#include <iostream>
using namespace std;
/*
<문제>
다이아, 철, 돌 곡괭이 각 0~5개 씩 가지고있음 / 피로도소모
재료가 같거나 덜 단단한 광물을 캘 때는 피로도 1, 한단계 업될 때마다 피로도 *5씩 상승
각 곡괭이는 종류 상관없이 광물 5개 캔 후엔 사용불가
곡괭이 랜덤 택 1
한번 사용시작 곡괭이는 사용불가 될 때 까지 사용
광물은 주어진 순서로만 캠
모든 광물을 캐거나, 곡괭이를 다 쓸 때까지 광물을 캠
-> 작업을 끝내기 까지 필요한 최소한의 피로도를 return하는 함수 완성하기
곡괭이 개수 나타내는 정수배열 picks(다이아, 철, 돌 순서) <=5 / 최소 1개이상씩 가지고있음
광물 순서 나타내는 문자열 배열 minerals <=50
-> diamond or iron or stone (string)
<풀이>
곡괭이를 선택하는 모든 경우의 수 재귀로 탐색 -> 계산 수 : 5^3(곡괭이 선택 경우의 수)*50(광물 수)
*/
int mine(vector<int> picks, vector<string> minerals, int cur_tired) {
//재귀 - 남은 곡괭이, 광물 배열, 현재 피로도를 넣어줬을 때, 피로도의 최소값 리턴
int min_tired = 987654321; //피로도 최소값
if ((picks[0] == 0 && picks[1] == 0 && picks[2] == 0)) return cur_tired; //곡괭이 모두 소진
if (minerals.size() == 0) return cur_tired; //광물 없음
if (picks[0] > 0) { //다이아곡괭이
vector<int> p = picks; vector<string> m = minerals; //복사해서 사용
p[0]--;
int plus_tired = cur_tired; //더하는 피로도값
for (int i = 0; i < 5; i++) {
if (m.size() == 0) break;
m.erase(m.begin()); plus_tired++;
}
//곡괭이, 광물, 피로도 적용 안료
int tmp = mine(p, m, plus_tired);
if (min_tired > tmp) min_tired = tmp;
//다이아곡괭이로 캤을 때 피로도 더하기 완료
}
if (picks[1] > 0) {//철곡괭이
vector<int> p = picks; vector<string>m = minerals; //복사해서 사용
p[1]--;
int plus_tired = cur_tired; //더하는 피로도
for (int i = 0; i < 5; i++) { //광물 캐기
if (m.size() == 0) break;//없으면 그만캐기
if (m[0][0] == 'd') //다이아몬드인 경우
plus_tired += 5;
else
plus_tired += 1;
m.erase(m.begin());
}
//곡괭이, 광물, 피로도 적용 안료
int tmp = mine(p, m, plus_tired);
if (min_tired > tmp) min_tired = tmp;
//철곡괭이로 캤을 때 피로도 더하기 완료
}
if (picks[2] > 0) {//돌곡괭이
vector<int> p = picks; vector<string>m = minerals; //복사해서 사용
p[2]--;
int plus_tired = cur_tired; //피로도
for (int i = 0; i < 5; i++) { //광물 캐기
if (m.size() == 0) break;//없으면 그만캐기
if (m[0][0] == 'd') //다이아몬드인 경우
plus_tired += 25;
else if (m[0][0] == 'i') //철인 경우
plus_tired += 5;
else
plus_tired += 1;
m.erase(m.begin());
}
//곡괭이, 광물, 피로도 적용 안료
int tmp = mine(p, m, plus_tired);
if (min_tired > tmp) min_tired = tmp;
//철곡괭이로 캤을 때 피로도 더하기 완료
}
return min_tired;
}
int solution(vector<int> picks, vector<string> minerals) {
int answer = 0;
/*
다이아 고를 경우, 철 고를 경우, 돌 고를경우 / 없으면 해당 단계 패스
*/
answer = mine(picks, minerals, 0);
return answer;
}
int main() {
int a, b, c;
cin >> a >> b >> c; //picks[0:2]
vector<int> picks;
picks.push_back(a); picks.push_back(b); picks.push_back(c);
vector<string> minerals;
string aa;
cin >> aa;
for (int i = 0; i < aa.size(); i++) {
string s; s += aa[i];
minerals.push_back(s);
}
cout << solution(picks, minerals) << endl;
return 0;
}
|
cs |
반응형