[Programmers 문제 풀이] 기지국 설치

안녕하세요. 오늘은 Programmers 기지국 설치 문제를 살펴보겠습니다.

 

문제는 아래의 링크에서 확인하실 수 있습니다.

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

코딩테스트 연습 - 기지국 설치

 

이 문제를 처음 본 순간 최소로 놓는 기지국의 개수를 묻는 문제이므로 당연히 이분 탐색으로 접근을 시도했습니다. 

 

하지만 이 문제는 이분 탐색으로 풀 필요가 없습니다. 왜냐하면, 이분 탐색의 mid = (start+end)/2의 값에 따라서 탐색 결과가 바뀌지 않습니다.

 

이게 어떤말이냐면, 어차피 이 문제는 최소로 놓을 수 있는 방법이 정해져 있기 때문에, 그 최소로 놓는 방법을 이분 탐색으로 찾는 과정이 필요 없고, 단지 최소 몇 개인지만 탐색하며 풀면 됩니다.

 

before에 이전 station이 cover할 수 있는 영역을 저장해 놓은 뒤, 다음 station의 시작 부분이 이전의 cover한 영역보다 더 이후에 존재한다면, 그 사이 값을 채워주시면 됩니다.

 

<소스 코드>

#include <iostream>
#include <vector>
using namespace std;
int solution(int n, vector<int> stations, int w)
{
    int answer = 0, div=(2*w+1), before = 0, cover = 0;
    for(auto a : stations) {
        cover = a-w-before-1; 
        if(cover >= 1) { 
            answer += cover/div;
            if(cover%div) answer++; 
        }
        before = a+w;
    }
    int lastCover = n-before;
    if(lastCover >= 1) {answer+=lastCover/div; if(lastCover%div) answer++;}
    
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.