[백준 13305번] [Kotlin] 주유소

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

13305번: 주유소

 

난이도 : 실버 3
태그 : 그리디

 

 

설명

그리디 알고리즘을 통해 풀 수 있는 문제입니다.

현재의 주유소보다 다음 주유소가 더 효율이 좋다면, 무조건 다음 주유소로 이동하는게 효율적입니다.

따라서, 현재 주유소보다 효율이 좋은 주유소를 탐색한 후,

해당 주유소까지 이동할 기름만 충전한 후, 해당 주유소르 이동합니다.

 

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    var st = StringTokenizer(readLine())
    val distance = Array(n) { if (it == 0) 0 else st.nextToken().toLong() }

    st = StringTokenizer(readLine())
    val fuel = Array(n) { st.nextToken().toLong() }

    var now = 0
    var money = 0L

    while (now < n - 1) {
        var next = now + 1
		
        // 지금보다 효율이 좋은 주유소 찾기
        while (next < n) {
            if (fuel[now] > fuel[next]) break
            next++
        }
        if (next == n) next--
        
        var needFuel = 0L

        for (i in now + 1..next) {
            needFuel += distance[i]
        }

        money += needFuel * fuel[now]
        now = next
    }

    println(money)
}