[프로그래머스] [2020카카오공채] 외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검 | 프로그래머스

 

둥그렇게 생긴 레스토랑의 구멍이난 외벽을 매꾸는 문제이다.

 

각 인원마다 커버 할 수 있는 거리가 다르며, 최소 인원을  찾는 문제였다.

 

첫날엔 시작위치에서 시계방향, 반 시계방향으로 2방향으로 재귀를 이용해 풀었으나 시간초과가 발생하였다.

 

시간초과를 줄이지 못해 첫날에 풀지 못하였다.

 

두 번째 도전엔 해설을 참고하여 풀었다.

 

* dist는 내림차순으로 정렬하였다. 큰 거리부터 채워나가는 것이 정답에 더 빠를 것이라 생각하였다.

* (1, 2, 3~ N) -> (2, 3 ~ N, N+1)  -> (3 ~ N, N + 1, N +2) 순서로 탐색을 하면 중복계산 없이 모든 방향을 체크 할 수 있었다.

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int g_weak[16];
int g_dist[9];
int distused[9];
int visited[16];
int result = 0;
int g_weakSize = 0;
int g_distSize = 0;
bool desc(int a, int b) { return a > b; }
void dfs(int x, int count)
{
	if (x == g_weakSize) {
		if (result > count) {
			result = count;
			return;
		}
	}
	if (count >= g_distSize) {
		return;
	}
	if (count >= result) {
		return;
	}
	int cpyVisited[16];
	memcpy(cpyVisited, visited, sizeof(visited));
	for (int k = 0; k < g_distSize; k++) {
		if (distused[k]) continue;
		int cur = g_weak[x];
		int end = g_weak[x] + g_dist[k];
		int next = 0;
		int sum = 0;
		distused[k] = 1;
		memcpy(visited, cpyVisited, sizeof(visited));
		for (int i = x; i < g_weakSize; i++) {
			if (visited[i] == 0 && g_weak[i] <= end) {
				visited[i] = 1;
				sum++;
			}
			else {
				break;
			}
		}
		if (sum != 0) {
			dfs(x + sum, count + 1);
		}
		distused[k] = 0;
	}
}

int solution(int n, vector<int> weak, vector<int> dist) {
	int answer = 0;
	sort(dist.begin(), dist.end(), desc);
	g_weakSize = weak.size();
	g_distSize = dist.size();
	for (int i = 0; i < g_weakSize; i++) {
		g_weak[i] = weak[i];
	}
	for (int i = 0; i < g_distSize; i++) {
		g_dist[i] = dist[i];
	}
	result = dist.size() + 1;

	if (g_dist[0] >= n) {
		return 1;
	}

	for (int i = 0; i < g_weakSize; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(0, 0);
		int nextVal = g_weak[0] + n;
		for (int j = 1; j < g_weakSize; j++) {
			g_weak[j - 1] = g_weak[j];
		}
		g_weak[g_weakSize - 1] = nextVal;
	}

	answer = (result == dist.size() + 1) ? -1 : result;
	return answer;
}