[Baekjoon, Python] 13305번 : 주유소

도입

백준 단계별 풀기 그리디 알고리즘 다섯 번째, 마지막 문제이다.

백준 13305번 문제, 입력, 출력

---

백준 13305번 입출력 예제 1, 2

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 입력을 보면, 도시 수(var_N), 각각의 거리(list_dist), 도시별 주유비(list_cost)까지 모든 정보를 받는다. 

 

2. 첫 도시에서 다음 도시로 가는 것은 무조건, 첫 도시에서 주유를 할 수 밖에 없고, 선택지가 없다. list_dist[0]*list_cost[0]로 이후 반환할 결과값(rtn)에 초기 세팅을 한다. 

 

3. 최소 주유값(var_min_cost)를 선언하고 각 도시에 경유 할 때마다(for문), 경유 도시의 주유비가 최소 주유값보다 싸면, 최소 주유값을 업데이트한다. 

 

4. 각 도시에 경유할 때마다(for문), rtn에 var_min_cost*list_dist[i]로 주유비를 계산해서 더해준다.   

---

코드

from sys import stdin

var_N = int(stdin.readline())
list_dist = list(map(int,stdin.readline().split()))
list_cost = list(map(int,stdin.readline().split()))

rtn = list_dist[0]*list_cost[0]
var_min_cost = list_cost[0]

for i in range(1,len(list_dist)):
    if var_min_cost > list_cost[i]:
        var_min_cost = list_cost[i]
    var_temp_expen = var_min_cost * list_dist[i]
    rtn += var_temp_expen

print(rtn)

---

마무리

그리디 알고리즘을 푸는 연습을 하면서 익숙해진 것인지, 마지막 문제가 크게 어려운 느낌이 들지 않았다. 문제 이해만 잘 한다면, 충분히 풀 수 있다.