[프로그래머스] 기지국 설치 - python

문제

• 프로그래머스 2018 서머코딩- 기지국 설치
• https://programmers.co.kr/learn/courses/30/lessons/12979

풀이

모든 영역을 커버할 수 있는 기지국을 최소로 설치하는 문제이다.
설치 할 기지국의 영역이 설치 된 기지국의 영역과 겹치지 않으면서, 최대로 활용되는 것이 최적해이다.
설치 된 기지국 영역에 속하지 않으면 기지국을 설치하고 기지국이 가질 수 있는 최대 영역(2*w+1)만큼 현재 위치를 이동시킨다. 영역에 속한다면 기지국 영역의 +1로 현재 위치를 이동시키고, index를 증가시켜 다음 기지국을 기준으로 다시 반복하여 최적의 설치 개수를 구할 수 있다.

코드

def solution(n, s, w):
    answer=0
    idx = 0
    locate = 1
    while locate <=n:
        if idx < len(s) and locate >= s[idx]-w:
            locate = s[idx]+w+1
            idx+=1
        else:
            locate += 2*w+1
            answer+=1
    return answer