[프로그래머스] 광물 캐기 (c++)

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

프로그래머스

 

[문제 요약]

 광물 별 강도와 곡괭이 별 위력이 주어지고,  광물 배열과 곡괭이 별 개수 배열이 주어진다. 광물을 캐는데 필요한 피로도는 (강도 / 위력)일 때, 피로도의 최소값을 구하여라. (곡괭이는 5개의 광물을 캘 수 있으며, 중간에 쓰다 버릴 수 없다.)

 

 

[풀이]

• 완전 탐색 문제로 O(2^N)에 풀린다.
• 곡괭이는 5개씩 묶어서 사용하므로, 5의 배수마다 새로운 곡괭이로 바꿀 수 있다.
  따라서 0~4, 5~9, ..., [5k, 5k + 4] 구간에 대한 다이아, 철, 돌 곡괭이에 대한 값들을 각각 저장한다.
• dfs로 사용가능한 곡괭이로 완전 탐색을 진행한다.
  캘수 있는 미네랄이 더이상 없거나, 곡괭이를 모두 사용했을 때 최소값을 구한다.

 

 

[코드]

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

using namespace std;

map<char, int> m = { {'d', 25}, {'i', 5}, {'s', 1} };
int p[3] = { 25, 5, 1 };
int mSum[11][3];

bool hasMoreMinerals(int sz, int idx) {
	return idx < (sz + 4) / 5;
}

bool hasAnyPicks(vector<int> &picks) {
	return 0 < picks[0] || 0 < picks[1] || 0 < picks[2];
}

void foo(vector<int> &picks, int sz, int idx, int cur, int &ans) {
	if (!hasMoreMinerals(sz, idx) || !hasAnyPicks(picks)) {
		ans = min(ans, cur);
		return;
	}

	for (int i = 0; i < 3; i++) {
		if (picks[i] > 0) {
			picks[i]--;
			foo(picks, sz, idx + 1, cur + mSum[idx][i], ans);
			picks[i]++;
		}
	}
}

int solution(vector<int> picks, vector<string> minerals) {
	int answer = 1e9;
	int sz = minerals.size();

	for (int i = 0; i < sz; i++) {
		int strength = m[minerals[i][0]];

		for (int j = 0; j < 3; j++) {
			int power = p[j];
			mSum[i / 5][j] += (strength - 1) / power + 1;
		}
	}

	foo(picks, sz, 0, 0, answer);

	return answer;
}

 

[코드 설명]

global) 문자열로 주어지는 광물에 대해 map<광물 이름, 강도>과 곡괭이의 위력을 배열로 만든다.

 

solution) 각 미네랄을 각 곡괭이로 채굴할 때의 값들을 5개씩 묶어서 mSum에 저장한다.

 

foo) dfs로 미네랄이 더 없거나, 곡괭이를 모두 소진했을 때의 최소값을 구한다.