外壁のチェック
アルゴリズムの資料は私も自分で解答したことがありますが、他の人との解答の比較を通じて、私が整理したこれらの資料はもっと良いアルゴリズムを学ぶためです.
プログラマ-外壁チェック
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;
}
}
Reference
この問題について(外壁のチェック), 我々は、より多くの情報をここで見つけました https://velog.io/@jkh2801/프로그래머스-외벽점검テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol