백준 - 주유소(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/13305

 

[문제 설명]

주유소에서 원하는만큼 기름을 살 수 있을 때, 목적지까지 최소 금액으로 기름을 사는 방법은?

 

[접근 방법]

처음 봤을 때는 2차원 배열을 활용한 DP인줄 알았다. 시간복잡도는 O(n^2)

그런데 입력의 개수가 10만개인 것을 보고 시간이 말이 안된다는 것을 깨달았다.

 

DP를 보기하고 문제를 계속 보면서 느낀 건 가격이 가장 저렴할 때 제일 많이 사야한다는 점이었다.

정확하게는 지금까지 지나온 주유소 중에서 제일 싼 곳에서 기름을 사는 것이다.

도시를 거쳐 이동할 때, 기름을 살 수 있는 곳은 지금까지 지나온 도시에서만 살 수 있다.

아직 도착하지 않은 주유소에서 기름을 살 수는 없다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val distances = br.readLine().split(" ").map { it.toLong() }.toLongArray()
    val prices = br.readLine().split(" ").map { it.toLong() }.toLongArray()
    var sum = 0L
    var minValue = prices[0]

    for (i in distances.indices) {
        if (prices[i] < minValue) {
            minValue = prices[i]
        }

        sum += minValue.times(distances[i])
    }

    println(sum)
}