[C/C++] Lv3 프로그래머스 - 외벽 점검

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

코딩테스트 연습 - 외벽 점검

- 접근법

취약 지점의 개수가 최대 15개까지 주어지고, 투입할 수 있는 친구의 수는 최대 8명까지 주어진다.

n은 200까지 주어지지만, 문제를 잘 읽고 생각해보면 결국 고려해야할 부분은 취약 지점들 사이의 간격들이기 때문에 n은 간격 계산에만 한번 사용되지 알고리즘 선택에는 영향을 끼치지않는다.

 

그러므로 우리에게 영향을 주는 2개의 변수의 최대크기를 보아하니, 완전탐색으로 풀릴 수 있다는 것을 직감적으로 느낄 수 있다.

 

결국 주어진 weak 배열을 통해 각 취약지점들 사이의 간격을 계산하고 그 간격을 주어진 dist 배열의 값들을 이용해서 간격들과 dist배열이 1:1 매칭이 될 수 있냐를 판단하는 것이다.

 

투입할 수 있는 친구의 수 MAXIMUM은 dist 배열의 크기이기 때문에 (문제에서는 8까지밖에 안들어온다)

나의 경우에는 이분탐색으로 x명으로 취약지점들을 모두 커버할 수 있다면 left로 탐색을 보내 더 작은 x명을 찾고

x명으로 취약지점을 커버할 수 없었다면 right로 보내 더 큰 x명으로 탐색했다.

 

완전탐색은 취약지점의 간격들을 x명으로 커버하려면 간격들중 x개를 빼야 하기 때문에 이 부분은 잘 생각해본다면 누구나 구현할 수 있을것이다.

---

- 소스코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#define INF 9999999
#define MINI(A,B) A>B ? B : A
using namespace std;
int dis[200],n_size,p_size;
int board[200],people[10];
stack<int> s_check;
bool flag=false;
int answer=INF;
bool checking() {
    int open_count=0,pop_count=0;
    int temp=0;
    vector<int> check_dis;
    for(int i=0;i<n_size;i++) {
        if(board[i]==0) {
            s_check.push(dis[i]);
            if(open_count==1) {
                pop_count++;
            }
        }
        else {
            open_count++;
            if(open_count==2) {
                temp=0;
                for(int j=0;j<pop_count;j++) {
                    temp+=s_check.top();
                    s_check.pop();
                }
                if(temp!=0) check_dis.push_back(temp);
                open_count=1;
                pop_count=0;
            }
        }
    }
    temp=0;
    while(!s_check.empty()) {
        temp+=s_check.top();
        s_check.pop();
    }
    if(temp!=0) check_dis.push_back(temp);
    sort(check_dis.begin(),check_dis.end());
    int left=0,right=0;
    for(int i=0;i<check_dis.size();i++) {
        while(true) {
            if(check_dis[i]<=people[right]) {
                right++;
                break;
            }
            else {
                right++;
            }  
            if(right>=p_size) return false;
        }
    }
    return true;
}
void DFS(int vertex,int picked,int count,int limits) {
    if(flag) return;
    if(vertex>=0) {
        if(picked==1) board[vertex]=1;
        else board[vertex]=0;   
        if(n_size-1-vertex+count<limits) return;
        if(count>limits) return;
    }
    if(vertex==n_size-1) {
        if(checking()) {
            flag=true;
            answer=MINI(answer,limits);
        }
        return;
    }
    DFS(vertex+1,0,count,limits);
    DFS(vertex+1,1,count+1,limits);
}
int solution(int n, vector<int> weak, vector<int> dist) {
    n_size=weak.size();
    p_size=dist.size();
    for(int i=1;i<n_size;i++) {
        dis[i-1]=weak[i]-weak[i-1];
    }
    sort(dist.begin(),dist.end());
    for(int i=0;i<p_size;i++) {
        people[i]=dist[i];
    }
    dis[n_size-1]=weak[0]+n-weak[n_size-1];
    int start=1,end=p_size,mid;
    while(start<=end) {
        mid=(start+end)/2;
        flag=false;
        DFS(-1,0,0,mid);
        if(!flag) {
            start=mid+1;
        }
        else {
            end=mid-1;
        }
    }
    if(answer==INF) answer=-1;
    return answer;
}