150. 13305(주유소) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())

road = list(map(int, input().split()))

city = list(map(int, input().split()))

result = 0
start = 0

for i in range(1, len(city)):
    if (i == len(city)-1):    
      for j in range(start, len(road)):
        result += road[j] * city[start]
    
    elif (city[start] > city[i]):
        for j in range(start, i):
          result += road[j] * city[start]    
        start = i  
        
    else:    
      continue
  
print(result)

문제요약

왼쪽 도시부터 오른쪽 도시까지 최소의 주유비용으로 가시오

설명

다음과 같이 원안에는 가스비용 선 위에는 도로 길이라고 하자.

현재 두번째 도시가 첫번째 도시보다 주유 비용이 싸다.

때문에 일단 두번째 도시로 이동하기 위해서 5*2의 비용을 지불하고 두번째 도시로 넘어가야 한다.

 

하지만 세번째 도시는 두번째 도시보다 가격이 비싸다.

때문에 두번째 도시에서 네번째 도시까지 갈 수 있게 주유한다면 최소의 비용으로 도착이 가능하다.

 

따라서

만약 비교 도중에 주유비가 더 적은 도시를 만난다면, 주유비가 최소라고 생각했던 부분을 기점으로 더 적은 부분이 도달 할 수 있을 정도 까지 주유를 하고 더 적은 쪽에서 부터 다시 주행을 시작하면 된다.

 

다시 예를 들면 

result = 0
start = 0

결과와 시작부분을 0으로 초기화 한다.

시작 부분은 지금까지 최소 부분을 담당한다.

 

for i in range(1, len(city)):
    if (i == len(city)-1):    
      for j in range(start, len(road)):
        result += road[j] * city[start]
    
    elif (city[start] > city[i]):
        for j in range(start, i):
          result += road[j] * city[start]    
        start = i  
        
    else:    
      continue

최소 주유비를 구하는 로직이다.

먼저 elif 부분 부터 설명 하겠다.

    elif (city[start] > city[i]):
        for j in range(start, i):
          result += road[j] * city[start]    
        start = i

지금까지 최소 비용(start) > 현재 비용 이라면 즉, 현재 비용이 더 낮다면,

start 인덱스 부터 현재 비용인덱스 전까지 도시 * 로드를 진행한다.

예를들어

 

입력이

7
3 4 2 2 4 5
8 9 5 4 2 7 1

다음과 같다면

지금까지 최소비용(start)는 8이고, 현재 최소 비용은 5이다.

따라서 8*3 + 8*4 를 진행한다.

그리고 지금까지 최소 비용을 현재 최소 비용의 인덱스로 저장한다.

 

    if (i == len(city)-1):    
      for j in range(start, len(road)):
        result += road[j] * city[start]

마지막 도시에 도달한 경우이다.(배열은 0부터 시작이기 때문에 길이 - 1이 마지막 도시이다.)

그러면 더이상 나아갈 곳이 없으니 지금까지 최소비용(start)을 가지고 진행되지 않은 도로의 값들을 계산해준다.

 

    else:    
      continue

continue를 통해서 현재 가지고 있는 비용이 최소이면 다음으로 넘어간다.