2020 KAKAO BLIND RECRUITMENT - 외벽 점검

2020 KAKAO BLIND RECRUITMENT - 외벽 점검

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

접근

처음에 외벽간의 거리를 계산하고, 이 거리보다 dist가 크다면 해당 거리와 해당거리랑 연관된 거리를 지우는 방식으로 했습니다.

당연히 실패했고, 한번에 2개이상의 취약점을 커버할 수 있는 친구들을 고려하지 못하는 방식 이었습니다.

결론적으로는 circular한 weak를 linear하게 쉬프트시킨 배열을 순회하는 형식으로 하고,

가능한 모든 순열(permutation)을 고려했습니다.

가령, weak = {1,2,3,4}인 경우에 내림차순 정렬 후 1명을 고를경우, 2명을 고를경우,3명을 고를경우, 4명을 고를경우 를 모두 순열로 고려했습니다.

내림차순을 한 이유는 가장 큰 친구부터 해보는것이 가장 최소의 친구숫자를 보장한다고 생각했기 때문인데요.

사실 이건 이전에 다른 문제(https://www.acmicpc.net/problem/17136)에서 크게 고전한 문제여서 금방 생각난것 같습니다.

후기

솔직히 너무 어려웠고 대회든 뭐든 이정도 난이도를 지금 마주치면 시간안에 풀 자신은 없습니다.

그래도 원형으로 된 데이터를 처리하는 새로운 방식을 알게 되었고(일반 circular queue 구현처럼 %n으로 구현하다가 죽을뻔..) 순열과 조합을 조금더 생각 할 수 있는 문제였습니다.

다음은 코드 전문입니다

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;

set<int> res;
vector<int> W;
vector<int> D;
vector<int> chk;
int N;
int init_pnt;
void dfs(int depth,int last_start,int maxn,int remain_pnt);
bool cmp(int x, int y);


int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
    sort(dist.begin(), dist.end(), cmp);
    deque<int> q;
    vector<int> t_v;
    for(int i = 0 ; i < weak.size() ;i++){
        q.push_back(weak[i]);
    }
    for(int i = 1 ; i  <= dist.size(); i++){ //how many friends
        for(int sh = 0 ; sh < weak.size(); sh++){
            
            t_v.clear();
            for(int a = 0 ; a < i ; a++) t_v.push_back(dist[a]);
            
            do{ //permutation dist.size() P i
                int pos = 0; //position which is needed to check
                for(int j = 0 ; j < i ; j++){ //combination friends (j'th friends)
                    int temp = t_v[j];
                    
                    for(int k = pos ; k < weak.size()-1; k++){ //go ahead
                        temp -= (q[k+1] - q[k]);
                        if (temp < 0) {
                            pos = k+1;
                            break;
                        }
                        else if(k == weak.size()-2){
                            return i;
                        }
                    }
                    if (pos == int(weak.size()-1) && (i-j) > 1) {
                        return i;
                    }
                    
                }
            }while(prev_permutation(t_v.begin(), t_v.end()));
            
            int t = q.front();
            q.pop_front();
            q.push_back(t+n);
        }
        
        
        
    }
    
    
    return answer;
}

bool cmp(int x, int y){
    return x>y;
}