[2020 KAKAO BLIND RECRUITMENT] 외벽 점검

문제풀이

 

구현은 쉽지만 문제 풀이 아이디어를 생각하는게 어려웠던 문제였다.

deque를 사용하여 0을 다시 넘는 경우를 11->1인 경우가 11 ->13 이 되도록 변경하여 계속 업데이트 해준뒤 

 

next_permutation을 사용하여 완탐을 진행하였다. 

먼저 갯수를 1부터 점점 키워나가며 -> 매 갯수 시작마다 deque를 초기화 -> 넥퍼뮤를 통한 완탐으로 모든 경우를 따져가며 성공시 해당갯수를 반환하여 끝내는 방식으로 구현하였다.

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
 
using namespace std;
 
deque<int> dq;
 
bool Permutation(vector<int> dist,int cnt){
    sort(dist.begin(),dist.end()); //큰게 앞에오게
    do{
        int start_idx = 0;
//        cout<<"dq"<<" : ";
//        for(int i=0;i<dq.size();i++)
//            cout<<dq[i]<<" ";
//        cout<<endl;
        for(int i=0;i<cnt;i++){
            int able_dist =dq[start_idx]+dist[i];
//            cout<<start_idx<<","<<dist[i]<<endl;
            int j=start_idx;
            for(;j<dq.size();){
                if(dq[j]<=able_dist){
                    j++;
                }
                else{
                    start_idx = j;
                    break;
                }
            }
            if(j==dq.size()){//끝까지 간경우
//                cout<<"success"<<endl;
//                for(int i=0;i<dist.size();i++){
//                    cout<<dist[i]<<" ";
//                }
//                cout<<"\n";
                cout<<cnt<<endl;
                return true;
            }
        }
    }while(next_permutation(dist.begin(), dist.end()));
    
    return false;
}
 
int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = 0;
    //cout<<"!!!"<<endl;
 
 
    
    //한번씩 시작지점이 되도록
    //앞에서 한번 뒤에서한번 시작해 줄거임.
    for(int i=1;i<=dist.size();i++){
        for(int i=0;i<weak.size();i++){
             dq.push_back(weak[i]);
        }
        for(int j=0;j<=weak.size();j++){
            if(Permutation(dist,i))
                return i;
            int temp = dq.front();
            temp += n;
            dq.pop_front();
            dq.push_back(temp);
        }
        dq.clear();
        
    }
    
    return -1;
}
 
int main(){
    int n = 12;
    vector<int> weak = {1,3,4,9,10};
    vector<int> dist = {3,5,7};
    cout<<solution(n,weak,dist)<<endl;
}
 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스