[백준/1366번] 킥보드로 등교하기 - G4/Python

https://www.acmicpc.net/problem/27977

문제

건덕이는 이번 학기 수강신청을 실패해 1교시 수업을 잔뜩 듣게 되었다! 건덕이의 등교 시간은 직장인의 출근 시간과 겹치는 시간대였기 때문에, 지하철을 타지 않고 킥보드를 구매해서 등교하기로 한다.

킥보드는 배터리 $1$을 소모해 거리 $1$만큼 이동할 수 있으며, 배터리를 모두 사용하면 킥보드가 멈추기 때문에 소진되기 전에 충전소에서 충전을 해야 한다.

건덕이의 집과 학교는 각각 $0$, $L$ 위치에 자리 잡고 있으며, 등굣길에는 총 $N$개의 킥보드 충전소가 순서대로 자리 잡고 있다. 충전하느라 시간을 낭비한다면 지각할 게 뻔하기 때문에, 건덕이는 등교 중에 최대 $K$번 충전소에 방문하기로 했다. 충전소에 방문하면 킥보드의 배터리가 가득 찬다.

킥보드의 가격과 배터리 용량은 비례하며, 건덕이는 집에서 킥보드를 가득 충전한 상태로 집을 나선다.

건덕이는 조건을 만족하는 킥보드 중에서도 가장 싼 킥보드를 구매하고자 한다. 건덕이가 구매할 킥보드의 배터리 용량을 구해보자.

입력

첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개의 정수 $A_i$가 공백으로 구분되어 주어진다.

풀이

def func(L, N, K, charger):
    left, right = max_dist, L
    result = 0
    while left <= right:
        mid = (left + right) // 2
        now,pos,cnt = mid, 0, 0
        for i in range(N+1):
            if charger[i] - pos > now:
                cnt += 1
                now = mid
            now -= (charger[i] - pos)
            pos = stones[i]
        if cnt <= K:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    print(result)


L, N, K = map(int, input().split())
charger = list(map(int, input().split()))
max_dist = max(charger[0], L - charger[-1])
for i in range(1, N):
    max_dist = max(max_dist, charger[i] - charger[i - 1])
charger.append(L)  # 마지막 도착점까지 포함
func(L, N, K, charger)

해결방법

충전용량 값을 가지고 이분 탐색을 진행하면 되는 문제.
충전용량으로 다음 충전소까지 갈 수 없는지 있는지를 판단해서 충전횟수를 구한 다음 충전 횟수가 제시된 최대 방문 횟수보다 작거나 같은 경우에 가능하다고  판단하고 결과를 출력하면 되는 문제.