설명

프로그래머스의 기지국 설치 문제다.

고정된 전송 범위를 가지는 기지국들이 일정 거리로 떨어져 있을 때 기지국의 전송 범위에 포함되지 않는 모든 곳에 데이터를 전송할 수 있도록 기지국을 최소한으로 배치하는 문제다.

풀이

사실 너무 어렵게 생각해서 그런지 풀이가 딱 떠오르지 않았다. 그래서 힌트를 참고한 결과 다음처럼 간단한 코드로 풀 수 있었다.

import math


def solution(n, stations, w):
    # 기지국의 갯수
    answer = 0

    # 기지국에서 담당할 수 있는 범위의 크기(양쪽 범위 + 기지국 자체).
    stationRange = 2 * w + 1
    # 이전 기지국에서 담당하는 타일의 다음 인덱스.
    # 즉 이 인덱스의 타일부터 기지국 설치를 고려해야 한다는 것.
    # 문제에서는 1-based indexing을 사용하기 때문에 초기값은 1로 설정.
    previousStation = 1
    for station in stations:
        # 현재 기지국에서 담당할 수 있는 범위의 왼쪽, 오른쪽 인덱스.
        rangeLeft = station - w
        rangeRight = station + w
    
        # 이전 기지국에서 담당하지 못하는 곳이 현재 기지국에서 담당하는 경우,
        # 즉 기지국의 담당 범위가 겹쳐있는 경우 별도의 기지국을 설치할 필요가 없음.
        if previousStation >= rangeLeft:
            # 현재 기지국 범위 바깥에서 기지국 설치를 고려해야함.
            # 그러므로 가장 오른쪽 인덱스의 다음 인덱스로 갱신.
            previousStation = rangeRight + 1
            continue
    
        # 현재 구간에 필요한 기지국의 갯수 계산, 추가.
        unavailableZone = rangeLeft - previousStation
        answer += math.ceil(unavailableZone / stationRange)
        
        # 현재 기지국 범위 바깥으로 인덱스 설정.
        previousStation = rangeRight + 1
    
    # 맨 마지막 기지국의 범위 뒤에도 기지국을 설치해야 하는 경우 추가.
    if previousStation <= n:
        # A ~ B 사이 숫자의 갯수는 B - A + 1이란 것을 잊지 말자.
        answer += math.ceil((n - previousStation + 1) / stationRange)
        
    return answer

레벨 3기 때문에 역시 어려운 방법으로 푸는 게 아닐까 생각했지만 매우 직관적이고 간단한 산술 연산으로 풀 수 있는 문제였다.
문제에서 주어진 예시인 위의 그림을 다시 보자. 그림으로만 봐도 빈 공간에 3개짜리 타일(기지국 범위 2 + 기지국 자체 1)을 채워넣으려면 3개가 필요하다. 타일은 단순히 기지국이 담당하는 범위기 때문에 3개를 딱 맞출 필요는 없으며 3개 이하의 타일은 하나의 기지국에서 담당할 수 있다.

하지만 6번부터 9번타일처럼 하나의 기지국에서 담당할 수 없는 범위라면 어떨까? 이때는 두 개의 기지국이 필요할 것이다. 왜냐면 4개의 타일을 채우기 위해서는 3개의 타일을 두 개 겹쳐놓는 것이 제일 효율적이기 때문이다. 이를 계산하는 공식은 단순하다. 필요한 타일의 갯수를 기지국 담당 범위의 크기로 나눈 결과를 올림 연산하는 것이다.

당연한 얘기지만 기지국을 필요에 따라 절반으로 나눌 수도 없는 일이기 때문에 무조건 자연수의 갯수로 설치해야 한다. 즉 남는 자투리 타일을 담당하기 위한 기지국 딱 하나만 더 설치하면 되는 것이다.

그리고 맨 마지막 기지국이 담당하지 못하는 타일이 남게 될 수 있으니 이 부분도 처리해주면 된다.

후기

사실 힌트를 보고 코드를 거의 다 작성했지만 계속 테스트 케이스가 몇 개씩 틀리곤 했는데 제대로 집중을 못해서 처음에는 소수 연산의 정확도쪽만 계속 살펴보았다. 하지만 알고보니 타일이 1부터 시작하는 문제의 특성을 고려하지 못했던 점과 맨 마지막 구간의 계산 부분의 간단한 실수가 원인이었다.

요즘은 DFS나 그래프, 트리 등 이런저런 알고리즘이나 자료구조를 쓰는 문제들만 계속 보다보니 간단한 문제도 계속 어렵게 생각하곤 하는데 위의 풀이처럼 직관적으로 풀이를 떠올릴 수 있도록 계속 연습해야겠다.