외벽 점검

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

카카오 kakao 백트래킹 BruteForce 브루트포스 기출 복습 구현 필수 추천 코테 코딩 프로그래머스

2020 KAKAO BLIND RECRUITMENT

처음에 bitmask + dp로 풀려다가 인덱스를 몇 차원으로 해야할지 무엇으로 구성해야할지 헷갈려서 그냥 Backtracing으로 접근하였다.

핵심은 모든 경우의 수(조합)에 대하여 vector v를 구성한다.

그리구, 구성한 vector v에 대하여 또 다시 weak에서 출발점을 달리하여 새로운 weak(temp)를 구성한다.(temp = 새로운 weak)

예시) 

weak = {3, 5, 7, 9}, n = 12라고 하고, 출발점을 7로 한다면, temp = {7, 9, 3+12, 5+12}로 구성한다. 

(첨부한 코드의 14 ~ 23번 째 줄)

그리고, 순서가 들어있는 vector v에서 원소를 하나씩 꺼내고, dist[v[v에 꺼낸 것]]를 pos에 저장한다. (26번 째 줄)

이때, pos가 얼마나 temp를 커버할 수 있는 검사한다.(첨부한 코드의 29 ~ 32번 째 줄)

마지막으로 a가 temp.size()와 같다는 것은 모든 weak를 커버했다는 의미이므로, ret에 최솟값과 비교하여 저장한다.

#include<bits/stdc++.h>
 
using namespace std;
 
int N, len, ans = 1e9;
bool use[10];
 
int simulation(vector<int> &v, vector<int> &weak, vector<int> &dist)
{
    int ret = 1e9;
 
    // 출발점
    for (int i = 0; i < weak.size(); i++) {        
        vector<int> temp;
 
        // weak를 출발점을 기준으로 새롭게 구성
        for (int j = i; j < weak.size(); j++) {
            temp.push_back(weak[j]);
        }
 
        for (int j = 0; j < i; j++) {
            temp.push_back(weak[j] + len);
        }
 
        int a = 0;
        for (int b = 0; a < temp.size() && b < v.size(); b++) {
            int pos = temp[a];
            pos += dist[v[b]];
            while (a < temp.size() && pos >= temp[a])
            {
                ++a;
            }
        }
 
        if (a == temp.size()) {
            ret = min(ret, (int)v.size());
        }
    }
 
    return ret;
}
 
void bt(vector<int> &v, vector<int> &weak, vector<int> &dist)
{
    if (!v.empty()) {
        ans = min(ans, simulation(v, weak, dist));
    }
 
    for (int i = 0; i < N; i++) {
        if (!use[i]) {
            v.push_back(i);
            use[i] = true;
 
            bt(v, weak, dist);
 
            use[i] = false;
            v.pop_back();
        }
    }
}
 
int solution(int n, vector<int> weak, vector<int> dist) {
    N = dist.size();
    len = n;
    sort(dist.begin(), dist.end());
 
    vector<int> v;
    bt(v, weak, dist);
 
    return ans == 1e9 ? -1 : ans;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    //vector<int> w = { 1, 5, 6, 10 }, d = { 1, 2, 3, 4 };
    //vector<int> w = { 1, 3, 4, 9, 10 }, d = { 3, 5, 7 };
    vector<int> w = { 1, 9 }, d = { 3 };
 
    printf("%d\n", solution(12, w, d));
 
    return 0;
}