外壁のチェック



アルゴリズムの資料は私も自分で解答したことがありますが、他の人との解答の比較を通じて、私が整理したこれらの資料はもっと良いアルゴリズムを学ぶためです.

プログラマ-外壁チェック


https://programmers.co.kr/learn/courses/30/lessons/60062
回答:Bit-Maskingを使用して外壁の必要人員を検査する
import java.util.*;

class Solution {
   	static int m;
	static int [] weak, dist;
	static int [][] cache; // 메모이제이션
	static final int INF = 987654321;
    public int solution(int n, int[] w, int[] d) {
   	m = n;
	weak = w;
	Arrays.sort(d);
	dist = new int [d.length];
	for (int i = 0; i < d.length; i++) { // 최소 인원으로 점검하기 위해 내림차순으로 정렬
		dist[i] = d[d.length-1-i];
	}
	cache = new int[dist.length+1] [1 << weak.length]; // // 1 뒤로 weak.length 만큼 0을 부여한 뒤 이진수로 전환
	for(int [] i : cache) Arrays.fill(i, -1);
		
	int answer = dp(0, 0);
    	return answer == INF ? -1 : answer;
    }

   private static int dp(int n, int mask) { // n명이 비트 mask 만큼 체크했다. 추가로 몇명이 더 필요하나?
	if(cache[n][mask] != -1) return cache[n][mask];
	if(mask == (1 << weak.length) - 1 ) return cache[n][mask] = 0; // 외벽을 전부 점검
	if(n == dist.length) return INF;
	int ret = INF;
	for (int i = 0; i < weak.length; i++) { // weak를 차례로 시작점으로 점검
		if((mask & (1 << i)) == 0) ret = Math.min(ret, dp(n+1, mask | bit(i, dist[n])) + 1);
		// mask의 i번째 비트가 활성화 되지 않으면 
	}
	return cache[n][mask] = ret;
	}
   private static int bit(int i, int j) { // 비트를 이용하여 외벽의 상태를 점검했는지 확인
	int cur = weak[i];
	int bit = 1 << i;
	while(true) {
		i = (i+1) % weak.length; // 다음 weak
		int next = weak[i];
		int curDist = next > cur? next-cur : m - cur + next; // weak 간의 간격 체크
		if(cur == next || curDist > j) break; // 전부 체크했거나 거리가 더 커졌으면 break
        	bit |= (1 << i); // i번째 비트 활성화
	}
	return bit;
	}
}