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

 

문제

 

13305번: 주유소

 

 

 

정답 소스코드 (Python)

 

n=int(input())
edge=list(map(int,input().split()))
vert=list(map(int,input().split()))
result=0
vert_min=min(vert)
skip_point=0
for i in range(n):
    recent_cost=vert[i]
    if skip_point>i:continue
    if vert_min==recent_cost:
        edge_sum=0
        for k in range(i,n-1):edge_sum+=edge[k]
        result+=edge_sum*vert_min
        break
    for j in range(i+1,n):
        if recent_cost>vert[j]:
            edge_sum=0
            for k in range(i,j):edge_sum+=edge[k]
            result+=edge_sum*recent_cost
            skip_point=j
            break

print(result)

 

 

풀이  (Python)

 

 

Point 1)  그리디 알고리즘

 

그리디 알고리즘은 문제를 작은 문제로 나누어서 각 작은 문제에서 최선의 선택을 하는 알고리즘이다.

모든 문제에서 최적이지 않지만, 그리디로 가능한 경우 다른 알고리즘에 비해 쉽게 구현할 수 있다는 장점이 존재하는 알고리즘이다.

 

이 문제의 경우 첫 정점에서 마지막 정점까지 이동하면서 각 간선의 최소 비용을 계산하는 문제이다. 정점에서 주유소를 들려 해당 가격에 주유를 할 수 있으며, 간선을 지나면 간선의 비용만 큼 기름이 차감된다.

기름을 최소의 비용으로 넣어서 끝까지 가기 위해서는 간선을 지날 때 기름이 없어지면 안 되고, 최대한 저렴한 주유소에서 주유를 많이 해야 한다. 

 

정점 1개 마다 각 단계로 가정하여 풀이하면 다음과 같다.

 

 

1. 가장 저렴한 주유소에서는 끝까지 갈 수 있는 연료를 주유하면 된다.

    if vert_min==recent_cost:
        edge_sum=0
        for k in range(i,n-1):edge_sum+=edge[k]
        result+=edge_sum*vert_min
        break

 

2. 현재 정점보다 더 작은 정점이 나오는 곳까지의 간선비용을 더해준다.

    for j in range(i+1,n):
        if recent_cost>vert[j]:
            edge_sum=0
            for k in range(i,j):edge_sum+=edge[k]
            result+=edge_sum*recent_cost
            skip_point=j
            break