백준 13305번 - 주유소

도시로 이동하는 동안 비용의 최솟값을 구하는 문제이다. 그리디 알고리즘의 기본적인 특성을 가지고 풀면 된다.

 

각 도시로 이동할 때의 최소 비용은 (기름 가격이 싼 도시의 기름 가격 * 다음 도시로 이동할 때까지의 거리의 합)이다. 그러므로 매번 도시를 이동할 때마다 가격이 싼 도시에서 기름을 최대한 넣어주면 될 것이다. 그러므로 처음부터 시작해서 기름 가격이 쌀 때마다 최솟값으로 갱신해주고 거리를 곱해서 합을 구해주면 된다.

 

##변수 선언 부분##
road = []
price = []
road_sum = 0
sum = 0
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    road = [int(x) for x in input().split()]
    price = [int(x) for x in input().split()]
    min = price[0] #첫 도시의 가격을 최솟값으로 지정
    for i in range(N-1): #N-1번만큼 반복
        if min > price[i] : #가격이 최소인 도시보다 더 싸면
            sum += road_sum * min #이전까지 더한 도로의 길이x가격 을 더해준다.
            road_sum = road[i] #최소인 도시의 road로 초기화
            min = price[i] #가격 갱신
            continue
        road_sum += road[i]
    sum += road_sum * min #마지막 항을 시행하지 않기 때문에 한번 더 계산

    print(sum)

별로 어렵지 않은 문제였지만, 그리디 알고리즘 문제임을 모르고 풀었으면 감이 잘 안왔을 것 같다.