説明:

これはプログラマーの基地局の設定題です.
一定の伝送範囲を有する基地局が一定距離離れている場合、基地局の伝送範囲外のすべての場所にデータを伝送できるように、基地局を最低限に配置する必要がある.

に答える

考えすぎたせいか、答えが思い出せない.したがって、ヒントを参照すると、以下のような簡単なコードで解くことができる.

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つ以下のタイルは1つの基地局が担当することができます.
しかし、6番から9番のタイルのように、1つの基地局で責任を負うことができない範囲ではどうなりますか?この場合、2つの基地局が必要になります.4個のタイルを充填するために、3個のタイルを重ね合わせるのが一番効率的だからです.これを計算する公式は簡単です.必要なタイルの数を基地局が担当する範囲の大きさで割って演算します.
当然ながら、必要に応じて基地局を半分に分けることはできないので、自然数に設定しなければならない.つまり、残りのタイルを担当する基地局をもう一つ設立するだけだ.
また、最後の基地局は責任を負うことができないタイルを残す可能性があり、この部分も処理することができます.

ポスト

実際、私はヒントを見て、ほとんどコードを書き終わったが、いくつかのテストケースが間違っていたが、私は集中できず、最初は少数の演算の精度の面で検査を続けた.しかし元々タイルは1からの問題の特性を考慮しておらず、最後の段の計算部分に簡単なミスがあった.
最近はDFS、グラフ、ツリーなどのアルゴリズムや資料構造を書く問題だけを見ているので、簡単な問題もずっと難しいと思っています.