프로그래머스[Programmers] - 광물캐기(C++)[LV2]

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

 

 

🔎문제 설명

• 곡괭이의 종류는 3개이고, 광물의 종류는 3개입니다.
• 곡괭이 하나로 광물을 5개 캘 수 있고, 5개를 연속으로 캐며, 5개를 캐면 다시는 사용하지 못합니다.
• 곡괭이로 광물을 캘 때, 광물에 따라 피로도가 다릅니다.
  • 다이아 곡괭이 -> 모두 피로도가 1
  • 철 곡괭이 -> 다이아 = 5, 나머지 =1
  • 돌 곡괭이 -> 다이아 = 25, 철 = 5, 돌 = 1
• 종료조건은 모든 곡괭이를 사용하거나, 더 이상 캘 광물이 없을 때입니다.
• 정해진 순서대로 광물을 캘 수 있으며, 우리는 최소한의 피로도를 사용해서 모든 광물을 캐거나, 모든 곡괭이를 사용해야 합니다.

😖문제 풀이 고민

입력 크기 제한이 그렇게 크지 않아서 , DFS를 사용한 완전 탐색을 해도 될 것이라고 생각했다.

 

💡문제 풀이

• 광물은 첫 글자만 봐도 구별할 수 있도록 문제에서 친절하게 설계를 했다.
  • 다이아몬드라면 25를, 철이라면 5를, 돌이라면 1을 배열에 넣어줬다.
    • 가장 까다로운 조건인 돌 곡괭이에 대한 피로도를 넣는 것이 편할 것 같아서 이렇게 결정했다.
• dfs로 완전 탐색을 한다.
  • 종료조건
    • picks [0], picks [1], picks [2]가 모두 0이라면 더 이상 곡괭이가 없다는 뜻이므로, 종료해야 한다.
    • 캘 광물이 더 이상 없다면 종료해야 한다.
      • 이 경우는 깊이 * 5(한 번에 캘 수 있는 양)이 광물의 전체 수 보다 클 경우이다.
    • 종료조건이라면 피로도에 대한 최솟값을 계속 갱신시켰다.
  • 곡괭이의 종류는 3개밖에 없어서 모든 경우를 탐색해도 시간 복잡도가 크지 않다고 생각했다.
    • 해당 곡괭이가 남아 있다면, 곡괭이의 종류에 따라 광물에 대한 피로도를 계산해서 넣어주고, 재귀함수를 호출했다.
    • 호출하기 전에는 해당 곡괭이를 감소시키고, 재귀 함수를 탈출한다면, 곡괭이를 다시 증가시켜 줬다.

💻코드

#include <iostream>
#include <string>
#include <vector>
#include <limits.h>
using namespace std;
int total=INT_MAX;
vector<int> result;
void funct(int idx, vector<int> picks,int tot,vector<string> minerals){
    int temp = 0;
    if((picks[0]==0 && picks[1]==0 && picks[2] ==0)||idx *5>=minerals.size()){ 
        //종료 조건. 곡괭이가 모두 0개이거나, 광물을 모두 다 캔 경우에는 그때의 피로도를 비교해서 최솟값을 저장.
        total=min(tot,total);
        return;
    }
    else{
        for(int i=0; i<3; i++){
            if(picks[i]!=0){ //곡괭이의 개수가 있다면
                picks[i]-=1;
                for(int j=idx*5; j<(idx+1)*5;j++){ //0~4 5    
                    if(j>=minerals.size()){ //만약 광물을 다 캤다면 종료
                        break;
                    }
                    if(i==0){ //다이아 곡괭이
                        temp+=1; //다이아 곡괭이는 어떤 광물을 캐더라도 모두 피로도가 1임.
                    }
                    else if(i==1){ //철 곡괭이
                        if(result[j]==25) //철 곡괭이는 다이아 굉물 빼고는 피로도가 1임.
                            temp+=5;
                        else
                            temp+=1;
                    }
                    else{ //돌 곡괭이는 피로도가 그대로 소요됨.
                        temp+=result[j];
                    }
                }       
                funct(idx+1,picks,tot+temp,minerals);
                temp=0; //재귀를 탈출했다면, 곡괭이를 원상복귀 해주고, temp값을 0으로 초기화
                picks[i]+=1;
            }
        }
    }
}
int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    for(int i=0; i<minerals.size();i++){     
        //광물의 첫글자만 봐도 비교가 되기에, 각 광물에 따라 값을 넣어줌. 비교하기 쉽게 25, 5, 1로 넣어줌. 
        switch(minerals[i][0]){
            case 'd':{
                result.push_back(25);
                break;
            }
            case 'i':{
                result.push_back(5);
                break;
            }
            case 's':{
                result.push_back(1);
                break;
            }
        }
    }
    funct(0,picks,0,minerals);
    answer=total;
    return answer;
}

 

😀느낀 점

• 광물의 대한 피로도를 무식하게 구했는데, 더욱 깔끔한 방법이 있다는 것을 발견했다.
  • 25 / 5 /1로 준 방법이 5로 나눈 몫이라는 것을 왜 생각 못했을까.. 만약 더 복잡한 값이었다면 난 아마 굉장히 노거다를 했을 것 같다.
• 프로그래머스는 다른 사람들의 코드 풀이가 공개돼서 정말 좋다.
  • 다른 사람의 코드를 보니 신기하게 푸는 사람이 굉장히 많네.. 난해하다.