[백준] 13305 주유소 - python

📖 문제 링크

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

📃 문제 설명

그리디 알고리즘을 이용하는 문제로

가장 왼쪽 도시에서 가장 오른쪽 도시까지 이동하는 최소의 기름 비용을 계산하는 문제이다.

👨‍💻 문제 풀이

생각해보면 쉬운 문제다.

가장 왼쪽 도시부터 기름 비용을 비교해 가장 적은 곳에서 계속 넣어주면 된다.

푸는 도중에 가장 적은 곳이라는 전제를 잊어버려 바로 앞의 도시와 비교하는 바람에 부분 성공을 맞긴했지만
가장 적은 비용 변수를 하나 만들어 그것에 대해 비교하면서 풀어냈다.

N = int(input())

count = 1
distance = list(map(int, input().split()))
city_cost = list(map(int, input().split()))

cost = distance[0] * city_cost[0]
min_cost = city_cost[0]

while count < N - 1:
  if (min_cost <= city_cost[count]):
    cost += min_cost * distance[count]
  else:
    cost += city_cost[count] * distance[count]
    min_cost = city_cost[count]
  count += 1

print(cost)

여기서 중요한 점은 처음 도시를 먼저 비용에 저장해두고 시작하는 점과 가장 적은 비용을 변수에 저장해두는 점이라고 생각한다.

2021.08.22