[그리디] 1826 연료 채우기, 1911 흙길 보수하기

7. 1826 연료 채우기

7.1. 유형파악

1. Greedy
2. 그리디는 정렬과 같이 나올 확률이 높다.
3. 바로 문제 유형이 보이지 않는다면 그리디를 의심해 볼 것
4. DP, Graph 알고리즘과 함께 나오는 경우도 있다.
5. 그리디 문제는 항상 최적의 해를 구할 수 있는지 의심해봐야 한다.

7.2. 해결과정

1. 현재 연료로 도달할 수 있는 주유소를 추린다.
2. 추린 장소 중 가장 멀리 떨어진 주유소로 방문해본다.
3. 해당 주유소에서 주유 후 다시 1-2번을 거친다.
4. 만약 방문할 수 있는 장소가 없다면 -1을 출력한다.

7.3. 소스코드

import heapq

n = int(input())
heap = []
for _ in range(n):
    heapq.heappush(heap, list(map(int, input().split())))
end, fuel = map(int, input().split())

cases=[]
cnt=0
while fuel < end:
    while heap and heap[0][0] <= fuel: # 연료로 도달할 수 있는 곳 체크
        place, f = heapq.heappop(heap)
        heapq.heappush(cases, [-1*f, place])

    if not cases:
        cnt = -1
        break

    f, place = heapq.heappop(cases) # 가장 멀리갈 수 있는 곳 체크
    fuel += -1*f
    cnt += 1

print(cnt)

8. 1911 흙길 보수하기

8.1. 유형파악

1. 그리디
2. 그리디는 정렬과 함께 출제되는 경향
3. 문제 유형 파악이 어려울 시 그리디 의심할 것
4. 종종 DP, Graph 알고리즘과 함께 출제된다.

8.2. 해결과정

1. ⭐힌트와 예제를 유심히 볼 것
2. 널빤지는 시작위치를 포함하고, 종료위치는 상관이 없다.
3. 또한 널빤지가 종료 위치를 초과해서 다음 웅덩이를 덮을 수 있다.

8.3 소스코드

n, l = map(int, input().split())
pool = [list(map(int, input().split())) for _ in range(n)]
pool.sort()
cnt = 0

for i in range(n):
    st, ed = pool[i]
    if (ed-st) % l != 0:
        length = (ed-st)//l + 1 ## 웅덩이를 다 덮지 못하는 경우 1개를 추가한다.
    else:
        length = (ed-st)//l ## 웅덩이가 딱 맞는 경우

    cnt += length
    new_ed = st + l*length

    if (i+1) < n:
        next_st = pool[i+1][0]
        if new_ed > next_st:    ## 널빤지가 웅덩이를 초과해서 다음 웅덩이까지 덮는 경우
            pool[i+1][0] = new_ed
print(cnt)