[프로그래머스 C++] 광물 캐기

[프로그래머스 C++] 광물 캐기

 

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

프로그래머스

---

 

해결전략

 

깊이우선탐색 DFS

그리디 Greedy

---

 

정답 코드 - DFS

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int answer;

// fatigue: 피로도, idx: 현재 인덱스, dia, iro, sto: 각 곡괭이의 수, 광물 벡터
void Shuffle(int fatigue, int idx, int dia, int iro, int sto, const vector<string>& m)
{
    if (idx >= m.size()) { // 모든 광물을 캔 경우
        answer = min(answer, fatigue); // 현재의 피로도와 이전의 최소 피로도 중 더 작은 값을 최소 피로도로 저장
        return;
    }
    if (dia == 0 && iro == 0 && sto == 0) { // 모든 곡괭이를 소모한 경우
        answer = min(answer, fatigue); // 현재의 피로도와 이전의 최소 피로도 중 더 작은 값을 최소 피로도로 저장
        return;
    }

    if (dia > 0) // 다이아몬드 곡괭이로 광물을 캔 경우
    {
        int newFatigue = fatigue; // 새로운 피로도를 계산
        for (int i = idx; i < idx + 5; i++) { // 다음 5개의 광물을 캐는 것을 시도
            if (m[i] == "diamond") newFatigue += 1;
            else if (m[i] == "iron") newFatigue += 1;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break; // 모든 광물을 캔 경우 종료
        }
        Shuffle(newFatigue, idx + 5, dia - 1, iro, sto, m); // 다음 광물로 이동하고 다이아몬드 곡괭이의 수를 감소
    }
    if (iro > 0) // 철 곡괭이로 광물을 캔 경우
    {
        int newFatigue = fatigue;
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") newFatigue += 5;
            else if (m[i] == "iron") newFatigue += 1;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(newFatigue, idx + 5, dia, iro - 1, sto, m);
    }
    if (sto > 0) // 돌 곡괭이로 광물을 캔 경우
    {
        int newFatigue = fatigue;
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") newFatigue += 25;
            else if (m[i] == "iron") newFatigue += 5;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(newFatigue, idx + 5, dia, iro, sto - 1, m);
    }
}

int solution(vector<int> picks, vector<string> m) {
    answer = 2147000000;
        
    Shuffle(0, 0, picks[0], picks[1], picks[2], m);

    return answer;
}

int main() {
    vector<int> test1 = { 1, 3, 2 };
    vector<int> test2 = { 0, 1, 1 };
    vector<int> test3 = { 0, 0, 0 };
    vector<int> test4 = { 1, 0, 0 };
    vector<int> test5 = { 0, 0, 1 };
    vector<int> test6 = { 1, 0, 1 };
    vector<int> test7 = { 5, 5, 5 };
    vector<string> testcase1 = { "diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone" };
    vector<string> testcase2 = { "diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond" };
    vector<string> testcase3 = { "diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond" }; 
    vector<string> testcase4 = { "diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond" };
    vector<string> testcase5 = { "diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond" };
    vector<string> testcase6 = { "stone", "stone", "stone", "stone", "stone", "iron", "iron", "iron", "iron", "iron", "diamond", "diamond" };
    vector<string> testcase7 = { "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond" };

    cout << solution(test1, testcase1) << "\n"; // 12
    cout << solution(test2, testcase2) << "\n"; // 50
    cout << solution(test3, testcase3) << "\n"; // 0
    cout << solution(test4, testcase4) << "\n"; // 5
    cout << solution(test5, testcase5) << "\n"; // 125
    cout << solution(test6, testcase6) << "\n"; // 10
    cout << solution(test7, testcase7) << "\n"; // 150
}

 

 

---

 

실수해서 고생한 부분

 

수정 전

void Shuffle(int fatigue, int idx, int dia, int iro, int sto, const vector<string>& m)
{
    if (idx >= m.size()) { // 광물을 다 캔 경우
        answer = min(answer, fatigue);
        return;
    }
    if (dia == 0 && iro == 0 && sto == 0) { // 곡괭이를 모두 소모한 경우
        answer = min(answer, fatigue);
        return;
    }

    if (dia > 0) 
    {
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") fatigue += 1;
            else if (m[i] == "iron") fatigue += 1;
            else if (m[i] == "stone") fatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(fatigue, idx + 5, dia - 1, iro, sto, m);
    }
    if (iro > 0) 
    {
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") fatigue += 5;
            else if (m[i] == "iron") fatigue += 1;
            else if (m[i] == "stone") fatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(fatigue, idx + 5, dia, iro - 1, sto, m);
    }
    if (sto > 0) 
    {
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") fatigue += 25;
            else if (m[i] == "iron") fatigue += 5;
            else if (m[i] == "stone") fatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(fatigue, idx + 5, dia, iro, sto - 1, m);
    }
}

 

각각의 재귀 호출에서 피로도가 누적되어야 하는데, 위의 코드에서는 각 재귀 호출마다 피로도(fatigue)가 초기화되어 버린다.

이를 수정하기 위해, 피로도를 누적하지 않고 새로운 피로도 값을 전달하는 대신, 이전 피로도에 새로운 피로도를 더한 값을 전달해야 한다. 아래의 코드를 확인하자.

 

 

수정 후

void Shuffle(int fatigue, int idx, int dia, int iro, int sto, const vector<string>& m)
{
    // ...

    if (dia > 0) 
    {
        int newFatigue = fatigue;
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") newFatigue += 1;
            else if (m[i] == "iron") newFatigue += 1;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(newFatigue, idx + 5, dia - 1, iro, sto, m);
    }
    if (iro > 0) 
    {
        int newFatigue = fatigue;
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") newFatigue += 5;
            else if (m[i] == "iron") newFatigue += 1;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(newFatigue, idx + 5, dia, iro - 1, sto, m);
    }

    if (sto > 0) 
    {
        int newFatigue = fatigue;
        for (int i = idx; i < idx + 5; i++) {
            if (m[i] == "diamond") newFatigue += 25;
            else if (m[i] == "iron") newFatigue += 5;
            else if (m[i] == "stone") newFatigue += 1;

            if (i == m.size() - 1) break;
        }
        Shuffle(newFatigue, idx + 5, dia, iro, sto - 1, m);
    }
}

 

 

---

 

정답코드 - 다른 풀이: DFS

 

#include <string>
#include <vector>
using namespace std;

// 각 picks가 광물을 채굴하는데 소모되는 피로도.
vector<vector<int>> consume = { {1, 1, 1}, {5, 1, 1}, {25, 5, 1} };

// depth: 현재 탐색 깊이, cnt: 에너지 소비량, picks: 각 픽엑스의 남은 사용 가능 횟수, m: 채굴할 광물의류
int DFS(int depth, int cnt, vector<int>& picks, vector<int>& m)
{
    // 재귀 호출의 종료 조건. 현재 깊이가 채굴할 광물의 총 개수보다 크거나, 모든 picks의 사용 가능 횟수가 0이 되면 현재까지 소비한 에너지를 반환
    if (depth >= m.size() || (picks[0] == 0 && picks[1] == 0 && picks[2] == 0))
        return cnt;

    int minCnt = INT32_MAX;
    int temp, j;
    for (int i = 0; i < 3; i++)
    {
        if (picks[i]) // 각 picks에 대해 깊이 우선 탐색
        {
            // picks를 사용하고, 해당 picks로 최대 5개의 광물을 채굴하면서 소비하는 에너지를 계산
            picks[i]--;
            temp = 0;
            j = depth;

            while (j < depth + 5 && j < m.size()) {
                temp += consume[i][m[j++]];
            }

            minCnt = min(minCnt, DFS(j, cnt + temp, picks, m)); // 재귀적으로 DFS를 호출하여 다음 광물을 채굴하고, 최소 에너지 소비량을 계산
            
            picks[i]++; // picks의 사용을 완료하면 사용 가능 횟수를 복구
        }
    }

    return minCnt;
}

// 각 픽엑스의 사용 가능 횟수와 채굴할 광물의 종류를 입력으로 받아 최소 피로도을 반환
int solution(vector<int> picks, vector<string> minerals)
{
    vector<int> m;

    // 채굴할 광물의 종류는 문자열로 입력되므로, 이를 consume 벡터의 인덱스에 맞게 변환하여 m 벡터에 저장
    // 다이아몬드, 철, 석탄은 각각 0, 1, 2로 변환
    for (string& iter : minerals)
    {
        if (iter == "diamond")
            m.push_back(0);
        else if (iter == "iron")
            m.push_back(1);
        else
            m.push_back(2);
    }

    // DFS 함수를 호출하여 최소 피로도 계산
    return DFS(0, 0, picks, m);
}

 

 

 

 

 

---

 

정답코드 - 다른 풀이: 그리디 Greedy

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int PICKTYPES = 3;    // 곡괭이의 종류 개수
const int CNT_PER_PICK = 5; // 한 번에 채굴 가능한 광물의 최대 개수

// 각 곡괭이가 다이아몬드, 철, 돌을 채굴할 때 발생하는 피로도
int fatigues[3][3] = { {1, 1, 1}, {5, 1, 1}, {25, 5, 1} };

struct Type{ // 광물의 종류를 나타내는 구조체
    int diamond, iron, stone;
};

bool Cmp(const Type a, const Type b) // 광물의 종류를 비교하는 함수
{
    if (a.diamond > b.diamond){ // 다이아몬드 개수가 많은 순으로 정렬
        return true;
    }

    if (a.diamond == b.diamond){ // 다이아몬드 개수가 동일한 경우
        if (a.iron > b.iron) // 철 개수가 많은 순으로 정렬
            return true;
        
        if (a.iron == b.iron) // 철 개수가 동일한 경우
            return a.stone > b.stone; // 돌 개수가 많은 순으로 정렬
    }

    return false;
}

int solution(vector<int> picks, vector<string> minerals) {
    
    vector<Type> v;
    int n = minerals.size();
    int total = 0;

    for (int iter : picks){
        total += iter;
    }

    for (int i = 0; i < n && v.size() < total; i += CNT_PER_PICK) // 각 턴에서 채굴 가능한 광물의 종류를 계산
    {
        int diamond = 0; // 다이아몬드 개수
        int iron = 0;    // 철 개수
        int stone = 0;   // 돌 개수

        for (int j = i; j < min(i + 5, n); j++) { // 각 턴에서 채굴 가능한 광물의 개수만큼 순회
            string mineral = minerals[j];

            if (mineral == "diamond") diamond++;
            else if (mineral == "iron") iron++;
            else stone++;
        }

        v.push_back({ diamond, iron, stone }); // 채굴 가능한 광물의 종류를 벡터에 추가
    }

    sort(v.begin(), v.end(), Cmp); // 광물의 종류를 정렬

    int answer = 0; // 최소 피로도

    for (Type iter : v) // 광물을 채굴하며 피로도를 계산
    {
        int pickIdx = -1; // 사용할 곡괭이의 인덱스

        for (int i = 0; i < PICKTYPES; i++) // 사용 가능한 곡괭이를 찾음
        {
            if (picks[i]) {
                pickIdx = i;
                break;
            }
        }

        if (pickIdx == -1) { // 사용 가능한 곡괭이가 없는 경우
            break;
        }

        picks[pickIdx]--; // 곡괭이를 사용

        // 피로도를 계산하여 누적
        answer += (iter.diamond * fatigues[pickIdx][0] + iter.iron * fatigues[pickIdx][1] + iter.stone * fatigues[pickIdx][2]);
    }

    return answer;
}