[Softeer] 택배 마스터 광우

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=581&sw_prbl_sbms_sn=99058

💻 문제 풀이 : C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> box;
vector<int> rail;
int visited[51];
int N, M, K;
int weight = 2134567890;

int getMax(int a, int b)
{
	return a > b ? a : b;
}

int getWeight(vector<int> v)
{
	int sum = 0;
	int time = 0;
	int bucket = 0;

	int i = 0;
	while (time < K)
	{
		if (bucket + v[i]> M) {
			bucket = v[i];
			time++;
			if (time >= K) break;
		}
		else
			bucket += v[i];
		sum += v[i];
		i++;
		if (i == v.size())
			i = 0;
		//time++;
	}
	return sum;
}

void DFS(int level)
{
	if (level >= N)
	{
		int tmp = getWeight(rail);
		if (weight > tmp) weight = tmp;
	}
	for (int i = 0; i < box.size(); i++)
	{
		if (visited[i] == 1) continue;
		rail.push_back(box[i]);
		visited[i] = 1;
		DFS(level + 1);
		rail.pop_back();
		visited[i] = 0;
	}
}

int main()
{
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		int weight;
		cin >> weight;
		box.push_back(weight);
	}
	DFS(0);
	//vector<int> tmp = {5, 10, 8, 19, 7};
	cout << weight;
	int de = 1;
	return 0;
}