2020 카카오 공채: 외벽 점검

[문제 링크]

코딩테스트 연습 - 외벽 점검

---

입력값이 작음에도 불구하고 완전탐색이 아닌 그리디 알고리즘으로 풀어볼려고 접근하다가 고생만 잔뜩 했다.

 

그냥 무난하게 모든 경우에 대해서 전부 시도해보면 되는 문제였다.

 

우선 거리 계산을 편하게 하기 위해 입력으로 주어지는 weak 배열의 각 지점 사이의 거리 차이를 계산해서 weakDist 배열에 저장하였다.

 

그다음 next_permutation() 함수를 통해 dist 배열로 만들 수 있는 모든 조합에 대해서 외벽 점검을 돌려 가장 최소 인원이 투입되는 경우를 구하면 된다.

---

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

const int INF = 987654321;

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

	vector<int> weakDist;

	for (int i = 0; i < weak.size(); i++)
	{
		if (i == weak.size() - 1)
			weakDist.push_back(n - (weak[i] - weak[0]));
		else
			weakDist.push_back(weak[i + 1] - weak[i]);
	}

	do
	{
		for (int i = 0; i < weakDist.size(); i++)
		{
			int pick = 0, pickDist = dist[0];

			int start = i;
			int end = start != 0 ? start - 1 : weakDist.size() - 1;

			while (start != end)
			{
				if (pickDist >= weakDist[start])
				{
					pickDist -= weakDist[start];
				}
				else
				{
					if (pick + 1 == dist.size()) break;

					pickDist = dist[++pick];
				}

				start = start + 1 == weakDist.size() ? 0 : start + 1;
			}

			if (start != end) pick = INF;

			answer = min(answer, pick + 1);
		}
	} while (next_permutation(dist.begin(), dist.end()));


	return answer == INF ? -1 : answer;
}

알고리즘 200일 프로젝트 - 139 day