프로그래머스 - 외벽 점검 - C++

hansol_Shin·2021년 5월 12일

알고리즘 프로그래머스

Algorithm

목록 보기

6/12

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

문제설명

원형 외벽의 크기 n이 주어지고, 각 수리 지점이 vector<int> weak로 주어진다.
외벽을 수리할 인원만큼의 vector<int> dist가 주어지고 각 dist[i]는 i번째 사람이 1시간 동안 외벽을 이동할 수 있는 거리가 주어진다.
수리 지점을 모두 수리할 수 있는 수리 인원의 최소 수를 구하는 문제이다.

접근 방법

weak의 최대 길이는 8, dist의 최대 길이 15로 주어지기 때문에 완전탐색 접근법을 사용해도 충분 할 것으로 판단한다.
weak가 원형의 개념이니 이를 컴퓨터에서 연산할 수 있도록 선형으로 변환한다.
dist를 next_permutation으로 모든 순열을 구하여 weak를 전부 순회하는지 탐색한다.
dist의 원소들로 weak의 모든 점을 탐색할 수 있는지? 또 있다며 그 때 최소 투입 인원(즉, 사용한 dist의 index+1)이 몇명인지 구하여 이에 대한 최소 값만 저장하면 된다.

풀이

#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = 0;
    vector<int> v;		// weak를 선형으로 변환하여 담아줄 vector
    for(int i=0;i<weak.size();i++){
        v.push_back(weak[i]);
    }
    for(int i=0;i<weak.size();i++){
        v.push_back(weak[i]+n);
    }
    
    sort(dist.begin(),dist.end());		// next_permutation을 사용하기 위해 정렬
    int min = 1000000000;			// 최소값을 담아둘 변수
    
    do{						// next_permutation 수행
        int s,e;
        for(int i=0;i<weak.size();i++){
            s = v[i];					// 출발점
            e = v[i+weak.size()-1];			// 도착점
            
            for(int k=0;k<dist.size();k++){
                s+=dist[k];				// 이동 후 위치점
                if(s>=e){				// weak를 다 순회했다면
                    if(min>k+1) min = k+1;		// 최소값이라면 갱신
                    break;
                }
                for(int t=0;t<v.size();t++){		// 다음 출발위치 선정
                    if(v[t]>s){
                        s = v[t];
                        break;
                    } 
                }
            }
        }        
    }while(next_permutation(dist.begin(), dist.end()));
    
    if (min == 1000000000) return -1;
    answer = min;
    return answer;
}