[DAY85] Algorithm : Station Installation

$N$개의 아파트에 4g 기지국을 5g로 변경하면서 전파가 닿지 않는 구간을 최소한의 기지국 증설로 커버하는 문제다. $N$이 최대 2억이므로 $O(N)$ 풀이는 불가능하며, 기존 기지국 사이의 "빈 구간 길이"만 계산하여 $O(\text{stations})$에 해결해야 한다.

---

❓ 문제 분석

• 목표: 전파가 닿지 않는 모든 구간(빈 공간)을 커버하기 위해 추가로 설치해야 할 기지국의 최소 개수 구하기.
• 제약 조건: 아파트 개수 $N$은 2억. bool 배열이나 루프를 돌며 하나씩 체크하면 시간 초과 및 메모리 초과 발생.
• 핵심 키워드: "최소 설치", "전파 도달 거리 W", "효율성".

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음엔 vector나 set을 이용해 전파가 닿는 아파트를 표시하려 했으나, $N$의 크기를 보고 바로 기각했다.
• 아파트 하나하나가 아니라 구간(Interval) 단위로 생각해야 함을 깨달았다.

2. 최종 해결책 (Solution)

• 전략: 현재 전파가 닿지 않는 시작점(position)을 관리하며, 기지국 사이사이에 있는 빈 구간의 길이(Len)를 구한다.
• 공식 유도:
  • 기지국 1개가 커버하는 최대 범위: $Range = 2 \times W + 1$
  • 빈 구간 길이: $Len = (\text{기지국 왼쪽 끝}) - position$
  • 필요한 기지국 수: $\lceil \frac{Len}{Range} \rceil$ (올림 처리)
• 알고리즘 흐름:
  1. position을 1로 초기화.
  2. stations 배열을 순회하며 빈 구간 길이 계산.
  3. 빈 구간이 있다면 필요한 기지국 수만큼 answer에 더함.
  4. position을 현재 기지국의 영향권 밖(station + W + 1)으로 갱신.
  5. 반복문 종료 후, 마지막 아파트까지 빈 구간이 남아있다면 추가 계산.

---

💻 코드 구현

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

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int position = 1; // 현재 전파가 닿지 않는 가장 왼쪽 아파트 번호

    // 기존 기지국들을 순회하며 앞쪽의 빈 공간 채우기
    for (int station : stations)
    {
        // 빈 공간 길이 = (현재 기지국 전파 시작점) - (현재 탐색 위치)
        int Len = (station - w) - position;
        
        // 빈 공간이 존재한다면
        if (Len > 0)
        {
            // 필요한 기지국 개수 더하기 (올림 나눗셈 공식 활용)
            // (Len + 분모 - 1) / 분모
            answer += (Len + (2 * w)) / (2 * w + 1);
        }
        
        // 탐색 위치 갱신: 현재 기지국 전파가 끝나는 지점의 바로 다음 칸
        position = station + w + 1;
    }

    // 마지막 기지국 이후에 남은 아파트 공간 처리
    if (position <= n)
    {
        int Len = n - position + 1; // 남은 구간 길이 (+1 주의)
        answer += (Len + (2 * w)) / (2 * w + 1);
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점 1: position 갱신 코드를 if (Len > 0) 블록 안에 넣는 실수를 했다. 이렇게 되면 빈 공간이 없을 때 position이 갱신되지 않아 무한 루프에 빠지거나 엉뚱한 계산을 하게 된다.
  • 해결: position 갱신은 조건문 밖으로 빼서 항상 수행되도록 수정했다.
• 문제점 2: 마지막 구간 처리를 반복문 안에서 수행하여 중복 계산이 발생했다.
  • 해결: 반복문이 완전히 끝난 후(for 문 밖)에 남은 구간을 한 번만 체크하도록 이동했다.
• 팁: 나눗셈의 올림 처리를 위해 ceil 함수 대신 (A + B - 1) / B 공식을 사용하면 정수 연산만으로 깔끔하게 처리 가능하다.

---

✅ 오늘의 회고

항목	내용
유형	구현, 수학, Greedy
체감 난이도	중 (N이 클 때의 효율성 처리가 관건)
복잡도	시간: $O(M)$ ($M$은 기지국 수), 공간: $O(1)$
새로 배운 것	나눗셈 올림 공식 (x + y - 1) / y, 구간 단위로 건너뛰며 계산하는 스위핑 기법