[Python/BOJ] 27977. 킥보드로 등교하기

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

27977번: 킥보드로 등교하기

문제

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

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

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

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

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

입력

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

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

출력

건덕이가 구매해야 할 킥보드의 배터리 용량을 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

# 1. left 반환 함수 정의
def return_left(info, l) :
    # 1-1. left 변수 정의
    left = -200_001
    # 1-2.
    for i in range(n) :
        # 1-2-1. 0번 인덱스의 경우
        if i == 0 :
            left = max(info[i], info[i+1] - info[i])
        # 1-2-2. 마지막 인덱스의 경우
        elif i == n - 1 :
            left = max(left, l - info[-1])
        # 1-2-3. 이외의 경우
        else :
            left = max(left, info[i+1] - info[i])
    # 1-3. left 반환
    return left
def solution(l, _, k, info) :
    # 2. left, right 설정
    left, right = return_left(info[:], l), l
    # 3.
    info += [l]
    while left <= right :
        # 3-1. mid 값 설정
        mid = (left + right) // 2
        # 3-2. 주유소 방문 횟수 체크
        cnt, now = 0, mid
        for idx, d in enumerate(info) :
            dist = d - info[idx - 1] if idx > 0 else d
            if now < dist :
                now = mid - dist
                cnt += 1
            else :
                now -= dist
        # 3-3. 방문 횟수가 k보다 큰 경우
        if cnt > k : left = mid + 1
        # 3-4. 방문 횟수가 k보다 작거나 같은 경우
        else : right = mid - 1
    # 4. 결과 출력
    print(left)

if __name__ == "__main__" :
    l, n, k = map(int, input().split())
    info = list(map(int, input().split()))
    solution(l, n, k, info)