[Programmers] 기지국 설치(c++)

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

프로그래머스

문제는 위 참고

결국 주어진 N으로 주어진 범위 외에 추가적으로 필요한 범위를 찾는 문제다.

나는 시작과 끝을 기준으로 작업했다.

위와 같이 주어졌을 때
(n = 9, station = {4}, w = 1)

1. station을 기준으로 -w-1 => 앞쪽의 남은 칸 개수
2. station을 기준으로 +w => 뒤쪽의 칸
3. n - 뒤쪽 칸 =>  뒤쪽의 남은 칸 개수
4. w가 1이므로 기지국이 커버하는 바운더리는 총 3
5. ∴ station -w(1) -1 = 2
6. 2는 하나의 기지국으로 커버가 가능 => ++answer;
7. n - (station +w) = 4
8. 4는 두개의 기지국으로 커버해야 한다. => answer+=2

∴   3이 나온다.

이번에는 station이 2개 이상일때를 알아보자

1. station의 첫번째의 앞쪽 번호를 계산한다.
2. 기지국 설치 수를 계산한다.
3. station의 첫번째의 뒤쪽 번호를 계산한다.
4. station의 두번째의 앞쪽 번호를 계산한다.
5. station의 두번째의 앞쪽 번호와 첫번째의 뒤쪽 번호를 뺀다
6. 나온 값을 기준으로 기지국 설치 수를 계산한다
7. ...station의 개수가 끝날때 까지 계산한다.
8. 마지막 부분을 계산하기 위해 n에서 마지막 station의 뒤쪽 번호를 뺀다.
9. 나온 값을 기준으로 기지국 설치 수를 계산한다.

위와 같이 계산을 하게 된다면

처음에는 2가 나오고(answer+1)
두번째는 1(answer+1)
세번째는 3이 나와 (answer+1)
총 3개의 기지국을 설치해야 한다.

음수나 0이 나오는 경우에는 answer에 수를 더하지 않는다. 설치할 필요가 없기 때문이다.

앞쪽 번호 계산은 
start  =  station[i] - w -1 - end;
뒤쪽 번호 계산은
end  =  station[i] + w;

answer계산은
(end-start)가 0 초과일 때 만
answer += (end-start)/bounds;
나머지가 있는 경우에도 더해줘야 하기 때문에
(end-start)%bounds 가 0 초과일 때
++answer;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;

    int bounds = (w * 2) + 1;
    int start = 0;
    int end = 0;

    sort(stations.begin(), stations.end(), less<int>());

    for (int i = 0; i < stations.size(); i++)
    {
        start = stations[i] - w - 1 - end;
        if (start > 0)
        {
            answer += start / bounds;
            if (start % bounds > 0)
            {
                ++answer;
            }
        }
        end = stations[i] + w;
    }

    start = n - end;

    if (start > 0)
    {
        answer += start / bounds;
        if (start % bounds > 0)
        {
            ++answer;
        }
    }


    return answer;
}