백준|1826번|연료 채우기

README·2023년 3월 27일
0

파이썬 PS풀이

목록 보기
133/136

문제 설명

가야 할 거리와 현재 가진 연료의 양, 주유소의 위치와 주유소가 가지고 있는 연료의 양을 입력받고 가야 할 거리를 모두 가려면 주유소에 최소한 몇 번 방문해야 하는지 출력하는 문제입니다.

작동 순서

  1. 주유소의 개수를 입력받고 주유소의 위치와 연료량을 입력받습니다. 이때 주유소가 위치별로 정렬되어있다는 보장은 없으므로 주유소를 위치순으로 정렬해줍니다.
  2. 가야 할 거리 L과 현재 가진 연료의 양 P를 입력받습니다.
  3. 시작점, 각 주유소, 도착점으로 이동하며 각각의 위치에서 연료의 양을 체크합니다. 만약 연료가 현재 위치까지 오는데 충분했다면 다음으로 넘어가고 부족한 경우 지금까지 지나온 주유소들중 가장 연료가 많은 순으로 멈춰서 주유를 한 것으로 합니다. 만약 지금까지 지나온 모든 주유소들에 들렀어도 현재 위치에 오는 것이 불가능하면 완주 가능 여부를 표시하는 arrive를 False로 설정합니다.
  4. 현재위치까지 오는 것이 가능했다면 현재 위치 주유소를 지나온 주유소의 목록(heap)에 삽입합니다.
  5. 도착점까지 도달했다면 완주 가능 여부에 따라 지금까지 방문한 주유소의 수(count)나 -1을 출력합니다.

소스코드

import heapq
import sys
N = int(sys.stdin.readline())

arrive = True
count = 0
heap = []
station = [[0, 0]]

for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    station.append([a, b])
station.sort()

L, P = map(int, sys.stdin.readline().split())

for i in range(1, N+2):
    if i < N+1:
        P -= station[i][0]-station[i-1][0]
    else:
        P -= L-station[i-1][0]

    while P < 0:
        if not heap:
            arrive = False
            break
        P -= heapq.heappop(heap)
        count += 1
    if i < N+1:
        heapq.heappush(heap, -station[i][1])

if arrive:
    print(count)
else:
    print(-1)
profile
INTP 개발자 지망생

0개의 댓글