Programmers / 기지국 설치 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 기지국 설치 (3단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def solution(n, stations, w):
    answer = 0
    current_pos = 1  # 현재 커버된 마지막 위치
    spread = 2 * w + 1  # 각 기지국이 커버하는 범위

    for station in stations:
        start_pos = station - w  # 현재 기지국이 커버하는 시작 위치
        if current_pos < start_pos:
            # 현재 커버된 마지막 위치와 다음 기지국 사이의 거리를 계산
            gap = start_pos - current_pos
            # 필요한 기지국의 개수를 추가
            answer += (gap + spread - 1) // spread  # 올림을 위한 계산
        current_pos = station + w + 1  # 현재 기지국이 커버하는 마지막 위치 + 1

    # 마지막 기지국 이후의 구간을 처리
    if current_pos <= n:
        gap = n - current_pos + 1
        answer += (gap + spread - 1) // spread

    return answer

 

1부터 근접한 기지국이 있는 위치의 차이를 구하고 거기에 설치해야하는 기지국 개수를 구하고

1이라는 위치에 다시 근접한 기지국이 영향을 주지 못하는 위치를 업데이트해서 구간을 잘라 개수를 구한다

 

---

※ 알아야 할 것

 

문제를 어떻게 풀지 생각을 하는게 중요한 것 같다.