[백준] 13305번 : 주유소 (python 파이썬)

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

 

 

from collections import deque
import sys
n = int(input())
road = list(map(int, sys.stdin.readline().split(" "))) #도로의 길이
oil = list(map(int, sys.stdin.readline().split(" "))) # 주유소의 기름 가격

graph = [[oil[0],0]] #[기름가격의 최솟값, 주요소까지의 거리]

min_oil = oil[0]
length = 0
for i in range(len(road)):
    if oil[i] < min_oil:
        min_oil = oil[i]
        graph.append([min_oil, length])
    length += road[i]


graph.append([0,length])
d = deque([[0,0,0]]) #현재 인덱스, 현재 기름, 비용
while d:
    d2 = d.popleft()
    idx, oil,cost = d2[0],d2[1],d2[2]

    if oil >= length:
        print(cost)
        break
    if oil < graph[idx+1][1]: #기름이 부족해 다음 노드로 못 갈 때,
        required_oil = graph[idx+1][1]-oil
        d.append([idx+1, graph[idx+1][1], cost+graph[idx][0]*required_oil])

 

---

문제 설명

n개의 도시가 있고, 각 도시마다 하나의 주유소가 있다.

 

주유소마다 리터당 기름값이 다르며, 도시마다 거리가 정해져있다.

 

처음 도시부터, 마지막 도시까지 가는 동안 필요한 기름을 사는 데, 필요한 최소 금액을 출력해라

 

 

 

 

---

문제 풀기까지의 사고과정

 

처음에는 단순한 모든 경우의 수를 방문하는 문제로 이해했다. 

 

따라서 현재 노드에서 가능한 모든 경우를 고려했다.

 

 

현재 노드에서 가능한 경우

 

1. 다음 노드로 간다.

2. 현재 노드를 한번 더 방문한다. 

 

 

위 두가지 경우를 모두 고려하면 경우의 수를 다 방문할 수 있다.

 

하지만 문제 조건을 잘 보자.

 

도시의 개수는 100,000 까지 존재하고, 도시의 거리는 1,000,000,000 이고, 리터당 가격은 1,000,000,000

까지 존재한다.

 

이것은 무엇을 의미할까?

 

 

문제의 범위가 엄청나게 크기 때문에, 리터를 하나씩 증가하거나, 모든 도시를 고려하면 시간 오류가 발생할 

것이다.

 

현재 노드를 한번 더 방문한다는 것은. 기름 1리터를 더 추가한다는 것인데, 도시의 거리가 엄청나게 

긴 경우에는 같은 수행을 최대 1,000,000,000 반복해야 한다는 것을 의미한다.

 

 

그렇다면 어떤 아이디어가 필요할까?

 

 

 

---

필요한 아이디어

 

이제 우리는 모든 도시를 방문하면 안된다는 점과, 기름을 1리터씩 추가하면 안된다는 점을 알았다.

 

다시 한번 문제를 생각해보자.

 

처음 시작하는 도시부터 끝 도시까지 기름 가격을 보면 어떤 아이디어가 떠올라야 할까?

 

바로 기름 가격은 점점 줄어들어야만 한다는 것이다.

 

만약 두 번째 도시의 기름 가격이 첫 번째 도시보다 비싸다면 방문할 필요가 있을까?

 

그렇다.

 

n번째 도시보다 먼 도시의 기름가격은 무조건 n번째 기름 가격보다 작아야 한다.

 

그러면 우리는 문제 해결 아이디어를 생각할 수 있다.

 

 

 

1. 처음 도시부터 순서대로 도시를 들르면서

2. 기름의 가격이 현재보다 낮으면

3. 그 도시까지의 거리만큼 기름을 충전하고, 그 도시까지 간다.

 

 

위 수행을 반복하다. 끝 도시만큼의 기름이 충전되면 정답을 반납한다. 

 

 

 

 

---

정답 흐름

 

입력 정보 정리 및 초기화

n = int(input())

road = list(map(int, sys.stdin.readline().split(" "))) #도로의 길이

oil = list(map(int, sys.stdin.readline().split(" "))) # 주유소의 기름 가격

graph = [[oil[0],0]] #[기름가격의 최솟값, 주요소까지의 거리]

 

 

 

현재까지의 최소 기름 가격 초기화

min_oil = oil[0]

 

 

 

거리 초기화

length = 0

 

 

 

도시를 돌면서 기름 가격을 줄여가며, 도시 정보를 graph에 저장

for i in range(len(road)):

    if oil[i] < min_oil:

        min_oil = oil[i]

        graph.append([min_oil, length])

    length += road[i]

 

 

 

 

처음 도시부터, graph의 도시까지 차근차근 방문하면서, 기름을 충전해 나간다.

while d:

    d2 = d.popleft()

    idx, oil,cost = d2[0],d2[1],d2[2]

    if oil >= length:

        print(cost)

        break

    if oil < graph[idx+1][1]: #기름이 부족해 다음 노드로 못 갈 때,

        required_oil = graph[idx+1][1]-oil

        d.append([idx+1, graph[idx+1][1], cost+graph[idx][0]*required_oil])

 

 

 

 

 

 

---

이 문제를 보며, 모든 경우를 방문하지 못할 경우의 사고 방식을 깨닫게 되었다.

 

그리디 문제와 dfs 문제가 섞일 수 있다는 점을 깨닫게 되었다.

 

입력정보를 보며, 어떤 방식을 써야하는지 생각할 수 있어야 함을 알았다.