공부 기록

문제 조건

레스토랑의 구조는 완전히 동그란 모양이고, 외벽의 총 둘레는 n(미터)이며, 외벽의 몇몇 지점은 취약한 지점들이 있다.

따라서 내부 공사 도중에 주기적으로 점검을 한다. 점검 시간을 1시간으로 제한된다.

친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하려고 한다.

편의상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타낸다.

친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동한다.

예제는 아래와 같고, 어디서든 출발하면서 특정 시간동안 많은 취약점을 찾도록 하면 되는 것 같다.

n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]
=> answer = 2

일단 1 <= n <= 200, weak의 길이는 1 이상 15 이하, dist의 길이는 1 이상 8 이하이다.

수의 범위가 굉장히 작아서 완전탐색을 해도 될 것 같다고 생각했다.

문제 풀이 과정은 아래와 같다.

1. 일단 모든 경우의 수(순열)을 뽑는다.

2. 순열이 외벽 점검을 만족하는지 확인하고 인원수를 업데이트 해 준다.

• weak = [1, 5, 6, 10]이라면 [1, 5, 6, 10], [5, 6, 10, 13], [6, 10, 13, 17], [10, 13, 17, 18]의 외벽점검을 시작한다.
• 적은 수의 순열부터 구한 다음에 min 값이 업데이트 되면 그 뒤는 계산하지 않도록 한다.

import java.util.*;
class Solution {
	public static int min = Integer.MAX_VALUE;

	public int solution(int n, int[] weak, int[] dist) {
		boolean[] isVisited = new boolean[dist.length];
		int[] output = new int[dist.length];

		for (int i = 1; i <= n; i++) {
			permutation(dist, output, isVisited, 0, n, i, weak);
			if (min != Integer.MAX_VALUE) {
				break;
			}
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		return min;
	}

	public static void permutation(int[] dist, int[] output, boolean[] visited, int depth, int n, int r, int[] weak) {
		int length = dist.length;

		if (min < r) {
			return;
		}

		if (depth == r) {
			if (isPossible(output, n, r, weak)) {
				min = Math.min(min, r);
			}
			return;
		}

		for (int i = 0; i < length; i++) {
			if (visited[i] != true) {
				visited[i] = true;
				output[depth] = dist[i];
				permutation(dist, output, visited, depth + 1, n, r, weak);
				visited[i] = false;
			}
		}
	}

	public static boolean isPossible(int[] output, int n, int r, int[] weak) {
		if (min <= r) {
			return true;
		}

		int length = weak.length;
		for (int start = 0; start < length; start++) {
			int userIndex = 0;
			int before = weak[start];
			boolean possibleUnit = true;

			for (int i = start; i < start + length; i++) {

				int now = weak[i % length];
				if (i >= length) {
					now += n;
				}
				if (now - before > output[userIndex]) {
					userIndex++;
					before = now;
				}

				if (userIndex >= r) {
					possibleUnit = false;
					break;
				}
			}
			if (possibleUnit) {
				return true;
			}
		}
		return false;
	}
}