[알고리즘 일기] 35. 빠르게 산 오르기

문제 35. (2021-06-04)

빠르게 산 오르기

신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다.

탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다.

함수 select_stops는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야겠죠.

참고로 모든 위치는 km 단위이고 용량은 L 단위입니다. 그리고 등산하기 전에는 이미 물통이 가득 채워져 있으며, 약수터에 들르면 늘 물통을 가득 채운다고 가정합시다.

예시

# 약수터 위치: [1km, 4km, 5km, 7km, 11km, 12km, 13km, 16km, 18km, 20km, 22km, 24km, 26km]
# 물통 용량: 4L
select_stops([1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26], 4)

처음에 4L의 물통이 채워져 있기 때문에, 장그래는 약수터에 들르지 않고 최대 4km 지점까지 올라갈 수 있습니다. 탈수 없이 계속 올라가기 위해서는 1km 지점이나 4km 지점에서 물통을 채워야겠죠?

최대한 적은 약수터를 들르면서 올라가야 하고, 마지막에 산 정상인 26km 지점의 약수터를 들르면 성공적인 등산입니다.

❧ 테스트 셋

def select_stops(water_stops, capacity):
    # Code

# Test
list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))

list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))

❧ 출력 예시

[4, 7, 11, 13, 16, 20, 24, 26]
[5, 8, 12, 17, 23, 28, 32, 38, 44, 47]

---

❧ 정답

def select_stops(water_stops, capacity):
    stops_root = []
    # for문의 시작점이 [1]이므로 처음에 [0]인덱스를 빼줌 
    water = capacity - water_stops[0]
    for i in range(1, len(water_stops)):
        distance = water_stops[i] - water_stops[i-1]
        # 현재 용량으로 다음 약수터를 갈 수 없으면
        # 이전 인덱스를 최종 리스트에 추가해줌
        if water < distance:
            stops_root.append(water_stops[i-1])
            water = capacity - distance
        else:
            water -= distance
    stops_root.append(water_stops[len(water_stops)-1])
    return stops_root


list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))

list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))

1️⃣ 시간 복잡도 : O(n)

2️⃣ 탐욕 알고리즘으로 접근

최적 부분 구조 : 정상에 다다르기 이전 단계까지의 최소 비용을 구한다.

탐욕적 선택 구조 : 최대한 가장 적은 용량만을 남기고 약수터에 들른다.

3️⃣ capacity 값을 if 문에서 사용해주어야 하므로 water(용량) 변수를 따로 만들어줌

---

개발 환경

Pycharm