백준 13305 - 주유소

문제

알고리즘 분류)

• 그리디 알고리즘

풀이

각 도시간의 거리와 도시에서의 기름값이 주어져 있을 때, 최소의 기름값을 구하는 문제이다
문제풀이의 요점은
-> 현재 기름값이 다음 기름값보다 비싸면 바로 다음 도시까지의 기름만 넣고
-> 그렇지 않으면 더 싼 기름값의 도시가 나오기 전까지 거리를 누적시킨다

테스트케이스1)
기름값:[1, 10, 100, 1000, 10000, 100000]
거리 : [5, 4, 3, 2, 1]
= 15*1 인 15의 결과값

테스트케이스2)
기름값:[100000, 10000, 1000, 100, 10, 1]
거리 : [5, 4, 3, 2, 1]
= (1000005)+(100004)+(10003)+(1002)+(10*1)
= 543210 의 결과값

이 나와주어야 한다

소스코드

python)

N = int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))

cur_price = price[0] #현재 기름가격
acc_distance = 0 #누적 거리
result=0

for i in range(N-1):
    if cur_price > price[i+1]: #기름넣는 경우
        acc_distance += distance[i]
        result += cur_price*acc_distance
        cur_price = price[i+1]
        acc_distance = 0.
    else:                    #안 넣는 경우
        acc_distance += distance[i]
result += cur_price * acc_distance

print(result)

마지막도시에서는 기름을 넣을 필요가 없으니 N-1번째 까지이다
루프가 끝나면 거리만 누적되어 있고 기름을 안넣은 경우를 대비하여 마지막으로 기름을 넣어주었다