[알고리즘/그리디] 13305번 : 주유소 - python

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

 

---

• 문제
• 소요 시간: 실패

---

• 설계하기(접근방법) 

1. 입력

1) 도시의 수를 입력받는다

2) 도시 간 거리를 입력받는다

3) 도시 각각의 리터당 기름가격을 입력받는다.

 

2. 알고리즘 생각

현재의 도시를 기준으로 그 다음 도시가 비싸다면 그 다음 도시의 거리까지 미리 주유하는 것이 더 효율적이다.

반대로 현재의 도시보다 다음도시의 기름값이 싸다면, 지금 가야할 거리만 주유한다.

반복문

1) 현재 최소값과, 현재 도시의 값을 비교한다

만약 현재가 더 싸다면 (현재 거리 * 현재 값)을 total에 더해준다

2)만약 현재 도시의 값이 더 싸다면, 그것을 현재 최소값으로 넣어준다.

 

3. total 출력하기

 

 

 

 

---

• 코드(출력)

city_num = int(input())
city_dis = list(map(int, input().split()))
city_oilprice = list(map(int, input().split()))

price = city_oilprice[0]
total = 0

for i in range(city_num - 1):
    if (price > city_oilprice[i]):
        price = city_oilprice[i]
    total += city_dis[i] * price

print(total)

 

---

• 얻어갈 부분

1. 처음 설계할 때, 최소값이 나올 때까지 모든 거리를 더하려고 하다보니 코드가 복잡해져서 실패했다.

for문을 순회하면서 더할 수 있다면 굳이 거리의 합을 따로 구하려고 하지 말고 그때그때 total에 더해주는 방법도 있다.

코드가 복잡해진다면 좀더 단순하게 생각해보자