programmers - 기지국 설치(파이썬)

programmers.co.kr/learn/courses/30/lessons/12979

 

코딩테스트 연습 - 기지국 설치

import math

# 그리디 문제
def solution(n, stations, w):
    cnt = 0
    start = 0
    for i in range(len(stations)):
        leftside = stations[i] - w-1
        cnt += math.ceil((leftside -start)/((2*w)+1))
       
        start = stations[i]+w
    cnt += math.ceil((n -start)/((2*w)+1))
    return cnt

처음에 풀때는 dp를 생각하다가 문제를 잘 읽고 생각을 하다보니 굳이... dp를 사용하는 경우는 만약에 각각 아파트에 값이 있고 최소나 최대를 판단할 때 일 꺼라고 생각했고,, 뭔가 거스름돈 문제랑 비슷한 느낌이 들어서 그리디로 풀게 되었는데 생각했던게 맞았다.