코딩테스트 -- 광물 캐기 - (프로그래머스 / C++)

 

 

프로그래머스

 

문제요약!

---

3가지의 곡갱이로 3가지 광물을 캘때 최소의 피로도를 구하는 문제입니다!

 

조건으로는

1. 한 곡갱이로 5개까지 캘수있다.

2. 한번 든 곡갱이는 끝까지사용해야한다.

3. 곡갱이를 모두 사용하면 완료된 것으로 취급한다.

 

이정도로 풀어낼수있을것 같습니다!

---

 

처음엔 단순 피로도 계산인줄 착각하고 있었는데 사실 곡괭이의 사용 순서가 중요한 문제였습니다.

 

만약 

["iron", "diamond", "diamond", "diamond", "iron", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond"]

이런식의 광물이 있고 

 

아래처럼 곡괭이가 있을때

[1, 1, 0]

 

다이아 곡괭이를 앞에 쓰느냐 뒤에 쓰느냐가 피로도에 영향을 주기 때문입니다

 

 

이 부분을 해결하기위해 저는 dfs 탐색 방법을 사용하여 해결하였습니다. 

 

 

 

그럼 코드 시작 하겠습니다!

 

가장먼저 입력이 "diamond"  처럼 단어로 입력되기에 이부분부터 처리해주었습니다. 

map<string, int>MineralList;                //광물들 이름
int AllList[3][3]={{1,1,1},{5,1,1},{25,5,1}}; // 각각 피로도

vector<int>MineralsIntList;

int ListSize=0;
int answer = 1250;

...

MineralList["diamond"]=0; //단어 처리
    MineralList["iron"]=1;
    MineralList["stone"]=2;
    
    for(string i : minerals){
        MineralsIntList.push_back(MineralList[i]);
    }

 

 

 

다음은 바로 dfs 시작!

인수로는 곡괭이의 갯수들과 현재위치, 현재까지의 피로도 합을 넘겨주었습니다.

 

void dfs(vector<int> &picks, int location,int sum){ // 곡갱이들, 현재 위치
    int sumList[3]={0,}; // 피로도 저장
    int savePoint=0;
    
    if(ListSize<=location || picks[0]+picks[1]+picks[2]==0){// 끝까지가거나 곡갱이다씀
        
        answer=min(answer,sum);
        return;
    }
    
    
    for(int i=location;i<location+5;i++){ // 5개씩 잘라서 구해주기
        
        if(i>=ListSize){
            savePoint=i;
            break;
        }
        sumList[0]+=AllList[0][MineralsIntList[i]];
        sumList[1]+=AllList[1][MineralsIntList[i]];
        sumList[2]+=AllList[2][MineralsIntList[i]];  // 각각의 곡갱이로 일을한것!
        
        savePoint=i;
    }
    
    
    
    for(int i=0;i<3;i++){//각각 출발
        if(picks[i]!=0){
            picks[i]-=1;
            dfs(picks,savePoint+1,sum+sumList[i]);
            picks[i]+=1;
        }
    }
    
    
}

 

 

5개씩 잘라서 처리해주고

중간에 끝나는 경우 (곡괭이를 다쓴경우, 5개씩 나누기에 모자란 경우)도 처리해주었습니다.

 

그 후는 일반적인 dfs! 

minerals의 길이가 짧아 가능했던것 같습니다...

 

 

 

 

 

ALL

#include <string>
#include <vector>
#include <map>

#include <iostream>
using namespace std;

map<string, int>MineralList;                //광물들 이름
int AllList[3][3]={{1,1,1},{5,1,1},{25,5,1}}; // 각각 피로도


vector<int>MineralsIntList;

int ListSize=0;
int answer = 1250;

//5 개씩 광물을 캔다....
//곡갱이의 갯수 picks   >> [다이아곡갱이 갯수, 철곡갯수, 돌곡갯수]
// 광물들의 순서 minerals   >> [순서~~~]
// 최소의 피로도는?


// >>> dfs로 찾기 가능?

void dfs(vector<int> &picks, int location,int sum){ // 곡갱이들, 현재 위치
    int sumList[3]={0,}; // 피로도 저장
    int savePoint=0;
    
    if(ListSize<=location || picks[0]+picks[1]+picks[2]==0){// 끝까지가거나 곡갱이다씀
        
        answer=min(answer,sum);
        return;
    }
    
    
    for(int i=location;i<location+5;i++){
        
        if(i>=ListSize){
            savePoint=i;
            break;
        }
        sumList[0]+=AllList[0][MineralsIntList[i]];
        sumList[1]+=AllList[1][MineralsIntList[i]];
        sumList[2]+=AllList[2][MineralsIntList[i]];  // 각각의 곡갱이로 일을한것!
        
        savePoint=i;
    }
    
    
    
    for(int i=0;i<3;i++){//각각 출발
        if(picks[i]!=0){
            picks[i]-=1;
            dfs(picks,savePoint+1,sum+sumList[i]);
            picks[i]+=1;
        }
    }
    
    
}

int solution(vector<int> picks, vector<string> minerals) {
    
    
    MineralList["diamond"]=0; //단어 처리
    MineralList["iron"]=1;
    MineralList["stone"]=2;
    
    ListSize=minerals.size();
    
    //5개씩 나눠야되네!
    //그럼 5개씩 해서 해결피로도 구하면 되는거 아닌감?
    
    
    for(string i : minerals){
        MineralsIntList.push_back(MineralList[i]);
    }
    
    
    
    dfs(picks,0,0);
    
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!