백준 1826 연료 채우기 파이썬

www.acmicpc.net/problem/1826

1826번: 연료 채우기

import heapq

N = int(input())
gas_stations = []
for _ in range(N):
    # 주유소까지의 거리, 채울수 있는 연료의 양
    a, b = map(int, input().split())
    heapq.heappush(gas_stations, (a, -b))
    
town_distance, my_gas = map(int, input().split())

if town_distance <= my_gas:
    print(0)
else:
    ans = 0
    gas_heap = []
    current_pos = 0
    
    while True:
        if current_pos+my_gas >= town_distance:
            print(ans)
            break    
            
        while gas_stations:
            info = gas_stations[0]
            if info[0] - current_pos <= my_gas:
                distance, gas = heapq.heappop(gas_stations)
                heapq.heappush(gas_heap, (gas, distance))
            else:
                break
            
        if gas_heap:
            print(gas_heap)
            max_gas, d = heapq.heappop(gas_heap)
            my_gas-=d-current_pos
            my_gas-=max_gas
            current_pos=d
            ans+=1
        else:
            if current_pos+my_gas < town_distance:
                print(-1)
                break
4
4 4
5 2
11 5
15 10
25 10

 

이 문제 많이 어려웠다.

그래도 결국 아무것도 보지 않고 혼자 해결했다. 직접 푸니 기분이 좋군..

이 문제는 그리디 이므로 탐욕적 사고를 할 필요가 있다.

핵심 아이디어는 이렇다.

내가 가진 기름으로 갈 수 있는 주유소 중 가장 많은 기름을 채울 수 있는 주유소를 방문해야한다. 이게 핵심이다.

 

1. 입력으로 받는 주유소 정보(주유소까지의 거리, 채울수있는 연료의 양)를 주유소까지의 거리를 기준으로 최소힙에 담는다.

2. 현재 위치에서 내가 가진 기름으로 마을에 도착할 수 있거나 더이상 움직일 수 없을때까지 순회하면서

3. 내가 가진 기름이 10 이라면 (주유소까지의거리 - 현재위치)  <= 10 이하인 주유소 정보를 꺼낸 후(pop) 각 주유소의 채울 수 있는 연료의 양 기준 최대힙에 담아준다. 예를들어 주유소까지의거리 가 10인데 내 현재위치가 4 면 6의 기름만 보유하고있어도 되기 때문에  (주유소까지의거리 - 현재위치) 를 하는것이다.

내가 현재 기름으로 도달할 수 없는 주유소를 만나면 그대로 loop 를 종료한다. 거리순으로 최소힙에 담겨있기때문에 이후는 모두 현재 보유한 기름으로 갈 수 없는 주유소이기 때문에 더이상 확인할 필요 없다.

4. 최대힙에 현재 내가 보유한 기름으로 갈 수 있는 주유소들이 들어있다. 이 중 가장 많은 기름을 주유할 수 있는 곳을 방문해야하므로 하나만 pop 해서 방문횟수(ans)에 +1 한 후,

내 현재 위치(current_pos)를 pop한 주유소의 위치로 수정.

내 보유 기름에서 pop한 주유소까지 이동한 거리만큼 보유 기름 감소

내 보유 기름에서 pop한 주유소에서 채울수 있는 연료의 양만큼 보유 기름 증가

위 과정을 반복하다가 더이상 방문할 주유소가 없는 경우(gas_heap 에 데이터가 없는 경우)

현재위치에서 내가 가진 기름으로 마을에 도달할 수 없는 경우 마을까지 도달하는것은 불가능하다. -1 출력후 루프 종료

루프 진행중, 현재위치에서 내가가진 기름으로 마을에 도달할 수 있는 경우 더이상 주유소를 확인할 필요없이 바로 현재까지의 방문횟수(ans) 출력후 루프 종료.

 

이제 이런문제도 풀어지는구나... 그리디 실력 조금 늘은듯..?

이제 그리디 몇문제만 더 풀어보고 DFS/BFS 로 넘어가야겠다.

 

 

--- 추가

다른분은 어떻게 풀었나.. 봤는데.. 너무 깔끔하네.. 

from sys import stdin
import heapq


def solution(N, stations, L, P):
    stations.sort(reverse=True)
    heap = []
    count = 0
    while P < L:
        while stations and stations[-1][0] <= P:
            dist, fuel = stations.pop()
            heapq.heappush(heap, -fuel)

        if not heap:
            break
        P -= heapq.heappop(heap)
        count += 1

    if L <= P:
        return count
    return -1


N = int(stdin.readline())
stations = [list(map(int, stdin.readline().strip().split(' '))) for _ in range(N)]
L, P = map(int, stdin.readline().strip().split(' '))

print(solution(N, stations, L, P))