[2020] 외벽 점검

#include <algorithm>

#include <string>

#include <vector>


using namespace std;

int solution(int n, vector<int> weak, vector<int> dist)
{
	int answer = 9;

	//dist를 내림차순으로 정렬
	sort(dist.begin(), dist.end(), [](int a, int b) { return a > b; });

	int ret;
	//weak 초기부터 시작하여 가장 작은 값에 n을 더해가며 n회 진행한다.
	for (int i = 0; i < n; i++)
	{
		//각 weak 버전에서 최소 인원을 찾기위한 초기 세팅
		vector<int> selected;
		ret = 1;
		int dsize = dist.size();
		bool allcover = false;

		//모든 취약점이 커버되지 않았고
		//투입 가능한 인원을 초과하지 않았을 때 까지 계속한다.
		while (ret <= dsize && !allcover)
		{
			allcover = true;
			selected.clear();
			//인원 수 만큼 가장 많은 지역을 움직일 수 있는 인원을 추가한다.
			for (int i = 0; i < ret; i++)
			{
				selected.push_back(dist[i]);
			}

			//선발된 인원들이 어떤 순서로 취약지점을 커버했을 때
			//모든 취약지점이 커버될 수 있는지 또는 커버할 수 없는지 
			//순열 조합으로 알아낸다.
			do
			{
				allcover = true;
				int si = 0;
				int wi = 0;

				//해당 인원이 커버할 지점을 선택한다.
				int start = weak[wi];
				int end = start + selected[si];
				while (1)
				{
					//해당 인원이 커버할 수 있다면
					if (start <= weak[wi] && weak[wi] <= end)
					{
						wi++;
						//마지막 취약지점이라면
						if (weak.size() <= wi)
						{
							allcover = true;
							break;
						}
					}
					//해당 인원이 커버할 수 없다면
					else
					{
						si++;
						//선발된 인원들로 모든 취약지를 커버할 수 없다면
						if (ret <= si)
						{
							allcover = false;
							break;
						}

						start = weak[wi];
						end = start + selected[si];
					}
				}

				//모든 지역이 커버되었다면 answer를 갱신한다.
				if (allcover)
				{
					answer = answer < ret ? answer : ret;
				}
			} while (prev_permutation(selected.begin(), selected.end()));

			//인원을 늘린다.
			ret++;
		}

		//첫번째 지점에 n을 더하여 정렬후 다시 진행하여
		//최소값을 탐색한다.
		weak[0] += n;
		sort(weak.begin(), weak.end());
	}

	//초기 answer값과 변화가 없다면 -1을 리턴한다.
	if (answer == 9)
	{
		return -1;
	}

	return answer;
}