백준 - 주유소(Swift)

백준 - 주유소(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

 나의 풀이

 

처음 풀이는 for문을 돌때마다 주유소의 나머지 값들 중에서 min을 구하고 남은 도로의 길이를 곱했는데 답은 나오지만 문제 조건의 N이 1억이기 때문에 다른 방법을 찾아야했다.

 

결국 1억이라는 숫자는 N혹은 logN으로 끝내야하기 때문에 한번만 탐색하면서 min값을 구하는 방식을 택했다.

 

import Foundation

let a = Int(readLine()!)!

let loads = readLine()!.components(separatedBy:" ").map{Int($0)!}
let prices = readLine()!.components(separatedBy:" ").map{Int($0)!}
var min = prices[0]
var sum = 0
for i in 0..<loads.count {
    if prices[i] < min {
        min = prices[i]
    }
    sum += min * loads[i]
}
print(sum)