[프로그래머스 기지국 설치] c++ (풀이,코드,그리디)

문제 링크

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

프로그래머스

 

문제

 

코드 및 풀이

 

이 문제는 굉장히 간단한 level3의 문제라고 생각합니다.

 

이 문제에서는 설치를 하는 경우의 수는 굉장히 많을겁니다. (최소라고 했을때)

이렇게 윗그림과 아랫그림을 예시로 보았을때 

윗그림에서의 첫번째 두개의 설치는 자리가 필수적으로 저곳에 들어갈 수 밖에 없습니다.

 

아래의 경우 첫번째 설치에 대해서 노란글씨로 어디든 설치를 하여도 상관이 없습니다.

 

우리는 이것을 코드로 어떻게 표현을 해줘야 할까?

기지국이 나올때까지 idx를 미뤄줍니다 -> idx = idx + 2 * w + 1 (코드에서는 range로 설정)

 

기지국이 나왔을때는? 윗그림을 보면 결국 설치가 기지국을 넘어갈일은 없다. 기지국을 기준으로 idx를 다시 미뤄주면 됩니다.

idx = stations[i] + w + 1

또한 idx가 stations[i](기지국임) +w -w 범위 내에 있어도 또한 idx = stations[i] + w + 1로 미뤄줍니다.

 

 

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int solution(int n, vector<int> stations, int w)

{

    int answer = 0;

    int range = 2 * w + 1;

    int idx = 1;

   

    for(int i = 0; i < stations.size();i++){

        if(idx < stations[i] - w){

            while(idx < stations[i] - w){

                idx = idx + range;

                answer++;

            }

            idx = stations[i] + w + 1;

        }else{

            idx = stations[i] + w + 1;

        }

    }

   

    while(idx <= n){

        idx += range;

        answer++;

    }

    return answer;

}