https://www.acmicpc.net/problem/13305
시간 2초, 메모리 512MB
input :
- 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)
- 인접한 두 도시를 연결하는 도로의 길이
- 왼쪽 도로부터 N-1개의 자연수
output :
- 최소 비용을 출력
조건 :
- 1km마다 1리터의 기름을 사용
딱 생각했던거를 반대로 실행하는 것으로 시간 복잡도를 줄였다.
우선적으로 사용하는 비용을 가장 줄이려면 기름값이 가장 작은 도시에서 도착지점까지 기름을 넣어야 한다. -> 가장 작은 값을 찾기 위해 min을 이용했고 모든 거리를 더하기 위한 sum을 사용한 것이 시간 복잡도에 문제가 되지 않았나 싶다.
뒤에서 부터 하지 말고 앞에서 부터 현재까지 가장 기름값이 싼 집을 저장해오면서 계산하자.
맨 처음엔 oil[0]의 값을 기름이 가장 싼 집으로 저장하고,
그 다음 부턴 minimum 과 oil[idx] 값을 비교하며 업데이트 해주자.
import sys
n = int(sys.stdin.readline())
distance = list(map(int, sys.stdin.readline().split()))
oil = list(map(int, sys.stdin.readline().split()))
minimum = oil[0]
ans = 0
for idx in range(len(distance)):
if oil[idx] < minimum:
minimum = oil[idx]
ans += minimum * distance[idx]
print(ans)
