프로그래머스 Level 3 기지국 설치[C++]

1. 문제 풀이

 미리 기지국이 설치된 곳을 기준으로 구역이 나뉘게 됩니다. 그 구역별로 따로 계산을 해야 일관성을 가질 수 있다고 추측하였습니다. 따라서 구역을 구분하는 작업을 먼저 합니다. 여기서 주의할 점은 미리 설치된 기지국들은 서로 인접한 곳에 위치할 수 있다는 가능성입니다. 예를 들어, stations[i] 위치에 설치된 기지국의 전파가 닿는 위치에 stations[i + 1]이나 stations[i - 1] 등이 설치될 가능성을 배제할 수 없습니다. 따라서 각 statons의 위치 cx와 전파 거리 w에 대해서 {cx - w, cx + w}와 같은 line을 만들어 저장한 다음 그리디하게 선들을 merge하는 작업을 했습니다.

 이로써 기지국의 전파가 닿지 않는 구역들이 구분되고 각 구역의 크기를 계산할 수 있습니다. 그 구역의 크기를 가져와 기지국을 설치할 수 있는 개수를 구하는 것은 단순 수학 공식을 사용하시면 됩니다. 작성한 코드의 변수명들이 조금 마음에 들지 않는데 수정하긴 귀찮아서 그냥 올립니다.

 

2. 코드

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
#define X first
#define Y second

vector<pi> segment;

int solution(int n, vector<int> stations, int w) {
    for(auto &cx : stations) {
        segment.push_back({max(1, cx - w), min(n, cx + w)});
    }

    vector<pi> part;
    part.push_back({0, 0});
    auto [tx, ty] = segment[0];
    for(auto [cx, cy] : segment) {
        if(tx <= cx && cx <= ty) {
            ty = cy;
            continue;
        }
        part.push_back({tx, ty});
        tx = cx;
        ty = cy;
    }
    part.push_back({tx, ty});
    part.push_back({n+1, n+1});

    w = (w << 1) + 1;

    int ans{};
    for(int i = 1; i < part.size(); i++) {
        int dist = part[i].X - part[i - 1].Y - 1; 
        ans += dist / w;
        ans += (dist % w != 0);
    }

    return ans;
}