사용자 도구

사이트 도구


ps:problems:boj:1826

연료 채우기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1826
문제명연료 채우기
레벨골드 2
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=10000
사용한 언어Python
제출기록32928KB / 92ms
최고기록56ms
해결날짜2022/02/23

풀이

  • 소위 주유소 문제의 변형. 주유소마다 판매 가격이 다른게 아니라, 판매량이 다르고 목표는 주유소 방문 횟수를 최소화하는것.
  • 기본 접근 방법은 주유소 문제와 같다. 주유소를 들를지 말지를 주유소 방문 시점에 결정하려는 생각을 버리고, 지금은 그냥 지난 다음에, 나중에 기름이 부족해지면 아까 주유소를 들렀던걸로 처리하는 것. 지나온 주유소들 중에서 가장 판매하는 양이 많은 주유소에서 샀던걸로 처리해야 하므로, 지나온 주유소들을 최대힙으로 관리하면 된다.
  • 입력 데이터에 주유소들이 정렬되지 않았다는 것이 주의하자.
  • 주유소들을 정렬하는데에 O(nlogn), n개의 주유소들에 대해서 각각 최대 한번의 heappush, heappop 연산이 필요하므로 여기에도 O(nlogn)이 걸린다. 그러므로 총 시간복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 1826. 연료 채우기".

- Problem link: https://www.acmicpc.net/problem/1826
- Solution link: http://www.teferi.net/ps/problems/boj/1826

Tags: [Greedy]
"""

import heapq
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    stations = []
    for _ in range(N):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        stations.append((a, b))
    L, P = [int(x) for x in sys.stdin.readline().split()]

    heap = []
    answer = 0
    movable_dist = P
    stations.append((L, INF))
    for dist, fuel in sorted(stations):
        while heap and movable_dist < dist:
            movable_dist += -heapq.heappop(heap)
            answer += 1
        if movable_dist < dist:
            print('-1')
            break
        heapq.heappush(heap, -fuel)
    else:
        print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
T᠎ X D K A
 
ps/problems/boj/1826.txt · 마지막으로 수정됨: 2024/02/08 03:56 저자 teferi