#13305 주유소 파이썬

 

 

 

www.acmicpc.net/problem/13305

13305번: 주유소

 

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]
m = cost[0]

# 나보다 작은 값이 나오면 그 이후로 그 값으로 계산 
# 마지막 나라의 가격은 사실상 사용되지 않으므로 무시 가능 
for i in range(1,n-1):
  if cost[i] < m : 
    total += dist[i] * cost[i]
    m = cost[i]
  else : 
    total += dist[i]*m

print(total)

 

+) 주의사항 

만약에 계속 min 함수를 이용해서 최솟값을 찾고자 하면 시간 초과 오류가 날 수 있음. 

처음에 아래와 같이 코드를 작성했더니 시간 초과 오류가 남. 

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]

# 가장 작은 값 이후로는 다 작은 값으로 계산 
e = len(cost)
while e > 1 : 
  cost = cost[:e] 

  small = min(cost)
  s_i = cost.index(small)

  # print("최소값은", small, "index : ", s_i)

  for i in dist[s_i:e] :
    total += small* i
    #print('total: ', total)
    #print(dist[s_i:e])

  e = s_i

if e == 0 : 
  total -= cost[0]*dist[0]

print(total)