-
[C++] 프로그래머스 광물 캐기알고리즘/프로그래머스 2023. 3. 23. 23:12반응형1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include <string>#include <vector>using namespace std;int answer = 999999999;vector<int> goc;vector<int> rem;bool check[16];void dfs(int s, int cnt, vector<string> minerals, vector<int> picks) {if(cnt == s) {int tired = 0;int tmp = 0;for(int i=0; i<minerals.size(); i++) {if(i/5 >= rem.size()) {break;}if(minerals[i] == "diamond") {if(rem[i/5] == 1) {tired += 1;}else if(rem[i/5] == 2) {tired += 5;}else if(rem[i/5] == 3) {tired += 25;}}else if(minerals[i] == "iron") {if(rem[i/5] == 1) {tired += 1;}else if(rem[i/5] == 2) {tired += 1;}else if(rem[i/5] == 3) {tired += 5;}}else if(minerals[i] == "stone") {if(rem[i/5] == 1) {tired += 1;}else if(rem[i/5] == 2) {tired += 1;}else if(rem[i/5] == 3) {tired += 1;}}}answer = min(tired,answer);return;}for(int i=0; i<3; i++) {if(picks[i] == 0) continue;picks[i] = picks[i] - 1;rem.push_back(i+1);dfs(s,cnt+1,minerals,picks);rem.pop_back();picks[i] = picks[i] + 1;}}int solution(vector<int> picks, vector<string> minerals) {for(int i=1; i<=3; i++) {for(int j=0; j<picks[i-1]; j++) {goc.push_back(i);}}if(minerals.size() < goc.size() * 5) {dfs(minerals.size()/5+1, 0, minerals, picks);}else {dfs(goc.size(),0,minerals,picks);}return answer;}
cs 백트래킹 + 구현
다이아 곡괭이, 철 곡괭이, 돌 곡괭이 순서대로 1,2,3 번호를 붙여 백트래킹 했다
곡괭이로 캘 수 있는 광물이 광물 수 보다 적을 때와 많을때를 고려해서 푸는것이 관건!
728x90반응형'알고리즘 > 프로그래머스' 카테고리의 다른 글
[C++] 요격 시스템 (3) 2023.04.17 [C++] 프로그래머스 연속된 부분 수열의 합 (0) 2023.04.13 [C++] 프로그래머스 리코쳇 로봇 (0) 2023.03.22 [C++] 프로그래머스 무인도 여행 (2) 2023.01.27 [C++] 백준 26091 현대모비스 소프트웨어 아카데미 (0) 2023.01.15