[알고리즘] 빠르게 산 오르기, 최적 부분 문제+ greedy, python(18)

def select_stops(water_stops, capacity):
    full_water = 1
    save_index = []
    i = 0
    
    while i < len(water_stops):
        if capacity*full_water - water_stops[i] > 0:
            i += 1
        elif capacity*full_water - water_stops[i] == 0:
            i += 1
            full_water += 1
            save_index.append(water_stops[i])
        else:
            i -= 1
            full_water += 1
            save_index.append(water_stops[i-1])
    return(save_index)
            
        
        
    

내가 계속 헤맸던 부분은 현재 약수터에서 안되면 이전 약수터로 어떻게 돌아가느냐?라는 것이었다. 그래서 for문을 사용하지 않고 while문을 사용하여 i를 업데이트(뒤로 혹은 앞으로) 했다. 

 

그런데 답지를 보니 그럴 필요 없이 이전 약수터라는 정보를 새로운  변수로 선언을 하면 되는 부분!

 

def select_stops(water_stops, capacity):
    # 약수터 위치 리스트
    stop_list = []

    # 마지막 들른 약수터 위치
    prev_stop = 0

    for i in range(len(water_stops)):
        # i 지점까지 갈 수 없으면, i - 1 지점 약수터를 들른다
        if water_stops[i] - prev_stop > capacity:
            stop_list.append(water_stops[i - 1])
            prev_stop = water_stops[i - 1]

    # 마지막 약수터는 무조건 간다
    stop_list.append(water_stops[-1])

    return stop_list