시간 복잡도를 줄이는 기술 3. 전처리 - 최소 비용 배열 활용하여 최소 에너지 비용 구하기

이런 유형의 문제 자주 나왔어서 기억해둘 것.

문제

n개의 서로 다른 장소가 일직선상에 주어집니다.

각 장소마다 에너지 1을 채우는데 필요한 비용이 다르며, 장소와 장소를 이동할 때는 에너지를 소모합니다.

각 장소마다 에너지 1을 채우는데 필요한 비용 과 장소와 장소를 이동할 때 소모하는 에너지가 주어질때, 제일 왼쪽 장소에서 제일 오른쪽 장소까지 이동할 때 드는 최소 비용을 계산하는 프로그램을 작성해보세요.

 

첫 번재 줄에는 장소의 개수를 나타내는 n이 주어집니다.

두 번째 줄에는 장소와 장소를 이동할 때 드는 에너지를 가장 왼쪽부터 차례대로 공백을 두고 주어집니다.

세 번째 줄에는 각 장소마다 에너지 1을 채우는데 드는 비용이 제일 왼쪽 장소부터 차례대로 주어집니다.

아이디어

가장 비용이 적게 드는 충전소에서 ‘최대한’ 많이 채운다.

현재 위치가 당장 비용이 가장 적게 든다면, 현재 위치에서부터 더 비용이 적게 드는 곳 까지는 현재 위치에서 채운다.

최소 비용을 기록한 record_arr를 만들고, 이동해야하는 거리 만큼 record_arr[i] * dist[i]로 최소 비용을 구하며 시간 복잡도를 줄인다.

 

record_arr : 이전 충전소 중 가장 비용이 작았던 값과 과 현재 충전소 값을 비교해서 계속해서 최소 비용을 기록한다.

 

 

코드

#최소 에너지 비용!!

#가장 비용이 작은 곳에서 최대한 많이 채운다 

n=int(input())
move_cost = [0]+list(map(int,input().split())) #길이:n
fill_cost= [0]+list(map(int,input().split()))#길이:n+1

record_arr = [1e9]*(n+1) #길이:n+1

for i in range(1,n+1): #1~n까지 비교, 배열 끝까지 비교
# [1e9, 1e9 vs fill[1], 1e9 vs fill[1] vs fill[2] ... ] 
    if record_arr[i-1] > fill_cost[i]:
        record_arr[i]= fill_cost[i]
    else:
        record_arr[i]=record_arr[i-1]


ans=0
for i in range(1,n): #1~n-1까지 비교 , 이동 비용 곱하는 만큼 비교 
    ans+=record_arr[i]*move_cost[i]
print(ans)