프로그래머스 광물 캐기 (C++)

안녕하세요~

오늘은 프로그래머스 광물 캐기 문제를 풀어봐요!

 

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

프로그래머스

 

곡괭이 종류 3가지와 광물 종류 3가지가 주어지고

어떤 곡괭이로 어떤 광물을 캐는지에 따라

피로도가 주어져요!!

 

저는 Vector<Map<string, int>>에

곡괭이 - 광물 피로도를 저장해놓고 풀었어요!

 

곡괭이의 개수가 담겨있는 int형 벡터와

광물 이름이 담겨있는 string형 벡터가 주어져요

 

광물은 주어진 순서대로만 캐기때문에

순서가 고정되어 있어서

최소 피로도를 계산하기 위해서는

곡괭이 선택 순서가 필요해요!

 

그래서 곡괭이의 종류를 모두 나열한 벡터를 선언하고

순열을 사용하여

각 순열마다 피로도를 계산해서 최솟값을 갱신하도록 했어요!

 순열은 next_permutation을 사용했답니다.

 

 

전체 코드 첨부할게용

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

using namespace std;

int tired = 0;
int minTired = INT32_MAX;

bool visited[16];

void Pick(vector<map<string, int>>& tiredMap, vector<int>& picks, const vector<string>& minerals, int pickedMineral, int picked, int cur)
{
    if (picked >= picks.size())
    {
        return;
    }

    for (int i = pickedMineral; i < pickedMineral + 5; i++)
    {
        if (i >= minerals.size())
        {
            return;
        }

        tired += tiredMap[picks[picked]][minerals[i]];
    }

    
    Pick(tiredMap, picks, minerals, pickedMineral + 5, picked + 1, cur + 1);
}

void Perm(vector<map<string, int>>& tiredMap, const vector<int>& picks, vector<int>& permedPicks,const vector<string>& minerals)
{
    if (permedPicks.size() == picks.size())
    {
        tired = 0;
        Pick(tiredMap, permedPicks, minerals, 0, 0, 0);
        minTired = min(tired, minTired);
    }

    for (int i = 0; i < picks.size(); i++)
    {
        if (visited[i])
        {
            continue;
        }
        visited[i] = true;
        permedPicks.push_back(picks[i]);
        Perm(tiredMap, picks, permedPicks, minerals);
        visited[i] = false;
        permedPicks.pop_back();
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;

    vector<map<string, int>> tiredMap(3);
    tiredMap[0]["diamond"] = 1;
    tiredMap[0]["iron"] = 1;
    tiredMap[0]["stone"] = 1;

    tiredMap[1]["diamond"] = 5;
    tiredMap[1]["iron"] = 1;
    tiredMap[1]["stone"] = 1;

    tiredMap[2]["diamond"] = 25;
    tiredMap[2]["iron"] = 5;
    tiredMap[2]["stone"] = 1;

    vector<int> picksVec;
    for (int i = 0; i < picks.size(); i++)
    {
        for (int j = 0; j < picks[i]; j++)
        {
            picksVec.push_back(i);
        }
    }

    do
    {
        tired = 0;
        Pick(tiredMap, picksVec, minerals, 0, 0, 0);
        minTired = min(tired, minTired);
    } 
    while (next_permutation(picksVec.begin(), picksVec.end()));

    return minTired;
}