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

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

프로그래머스

 

브루트포스로 풀었다.

사용할 곡괭이 딱 10개만 정해서 백트래킹으로..

 

다른 사람들 풀이 보니까 그리디가 있긴 했는데, '이렇게 명백한 백트래킹에선 빠르게 백트래킹 구현하는게 낫지 않나?' 싶다.

백트래킹 코드야 워낙에 정형화 되어있으니, 손가락만 빠르다면 그리디보다 더 효과적일 것 같다.. ㅋㅋ

 

이것만 떡하니 올리긴 뭐해서 챗지피티한테 코드 설명만 부탁해서 첨부하겠다~

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

using namespace std;

vector<int> allPicks;
vector<string> allMinerals;
int arr[10];
int brr[10];
bool isused[10];
int picksSum;
int tiredSum = 99999999;

void func(int k) {
    if(k == picksSum) {
        int tempTiredSum = 0;
        for(int i = 0; i < allMinerals.size(); i++) {
            if(brr[i / 5] == 0) {
                break;
            }
            if(allMinerals[i][0] == 's') tempTiredSum += 1;
            else {
                if(brr[i / 5] == 3 && allMinerals[i][0] == 'd') tempTiredSum += 25;   
                if(brr[i / 5] == 3 && allMinerals[i][0] == 'i') tempTiredSum += 5;   
                if(brr[i / 5] == 2 && allMinerals[i][0] == 'd') tempTiredSum += 5;   
                if(brr[i / 5] == 2 && allMinerals[i][0] == 'i') tempTiredSum += 1;   
                if(brr[i / 5] == 1 && allMinerals[i][0] == 'd') tempTiredSum += 1;   
                if(brr[i / 5] == 1 && allMinerals[i][0] == 'i') tempTiredSum += 1;   
            }
        }
        tiredSum = min(tiredSum, tempTiredSum);
        return;
    }
    
    for(int i = 0; i < picksSum; i++) {
        if(!isused[i]) {
            brr[k] = arr[i];
            isused[i] = 1;
            func(k + 1);
            isused[i] = 0;
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    allPicks = picks;
    allMinerals = minerals;
    int coun = 0;
    picksSum = min(10, picks[0] + picks[1] + picks[2]);
    for(int i = 0; i < 3; i++) {
        while(picks[i]) {
            arr[coun++] = i + 1;
            picks[i]--;
            if(coun == 10) break;
        }
        if(coun == 10) break;
    }
    
    func(0);
    
    return tiredSum;
}

이 코드는 주어진 광물을 캐기 위해 곡괭이를 조합하는 모든 경우의 수를 탐색하여 최소한의 피로도를 구하는 함수인 solution을 구현한 코드입니다.

 

코드에서 사용되는 변수들은 다음과 같습니다:

• allPicks: 다이아몬드, 철, 돌 곡괭이의 개수를 담은 벡터
• allMinerals: 광물들의 순서를 담은 문자열 벡터
• arr: 모든 곡괭이 종류를 포함하는 배열
• brr: 현재 선택한 곡괭이들을 저장하는 배열
• isused: 곡괭이가 사용되었는지 여부를 나타내는 배열
• picksSum: 곡괭이 종류의 총 개수를 저장하는 변수
• tiredSum: 최소 피로도를 저장하는 변수

주요 함수:

1. func(int k): 재귀적으로 모든 곡괭이를 선택하는 함수. k는 현재 선택한 곡괭이의 개수를 나타냅니다. 모든 곡괭이를 선택한 경우에는 해당 조합에 대한 피로도를 계산하고, 최소 피로도인 tiredSum을 갱신합니다.
2. solution(vector<int> picks, vector<string> minerals): 주어진 광물을 캐기 위해 가능한 모든 곡괭이 조합을 구하여 최소한의 피로도를 반환하는 함수입니다. 입력으로 주어진 picks 벡터에서 다이아몬드, 철, 돌 곡괭이의 개수를 읽어와 arr 배열에 모든 곡괭이 종류를 저장합니다. 그리고 func(0)을 호출하여 모든 곡괭이 조합을 탐색하고 최소 피로도를 구합니다.

코드에서 func 함수를 통해 재귀적으로 모든 곡괭이 조합을 탐색하고, 각 조합에 대해 광물을 캐기 위한 피로도를 계산하고 최소 피로도를 구하게 됩니다. 이를 통해 모든 광물을 캐기 위한 최소한의 피로도를 반환합니다.