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

출처: unsplash.com

 

주유소(13305번)

Silver 3

#그리디 알고리즘

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

 

문제 내용

 

 

문제 접근

사진 1-1

이 사진에서 원 안의 수가 1L당 기름의 값이고 원 사이의 연결된 선이 도시 간 도로의 길이일 때, 적은 기름값으로 첫 번째 도시에서 마지막 도시까지 이동할 수 있는 경우를 구해야 한다.

위 예제에서는 5원짜리 2L를 첫 번째 도시에서 구매해 주고, 2원짜리 4L를 두 번째 도시에서 구한다. 4L로 2, 3번째 도로를 지날 수 있다. 그래서 정답은 18이다.

 

가장 적은 기름값이 들어야 하기 때문에 기름값이 이동하면서 증가하면 안 된다.

세 번째 경우에는 원래는 1L당 4원이 필요하지만 이전 도시의 2원이 더 저렴하기 때문에 2원만 쓰고도 3번째 도로를 이용할 수 있다.

다시 적어 보면, 총 3단계로 요금을 청구한다.

1. 기름 2L, 1L당 5원이므로 10원

2. 기름 3L, 1L당 2원이므로 10 + 6원

3. 기름 1L, 1L당 4원이지만, 2번에서 1L를 더 담아 오면 10 + 6 + 2 = 18원

위와 같은 단계로 이루어진다.

3번째의 경우는 그냥 2원짜리 기름 1L를 추가로 구매했다고 생각하면 규칙을 찾을 수 있다.

 

바로 1L당 기름 값이 내림차순이어야 한다.

입력 예제 1부터 처음에는 리터당 기름 값이 5원이었다가 2원이 된다. 3번째에서는 4원이지만, 2원짜리 1L를 구매한 것과 다름이 없어서 똑같이 2원이다.

5 -> 2 -> 2 순으로 리터 당 기름값이 작아졌다.

이를 이용해서 다음 도시의 리터 당 기름값이 이전 도시보다 비싸면 이전 도시의 기름값을 이용해 기름을 구입한다.

다르게 말하면 이전 도시에서 현재 도시의 도로를 지나는 데 필요한 기름까지 같이 산다고 생각하면 된다.

 

<조건 1>

그러면 이전 기름값보다 현재 기름값이 더 싸면 어떻게 해야 할까? 당연히 현재의 기름값으로 기름을 구매해야 한다.

그 이후의 도시에서도 다음 도시의 기름값이 더 싸질 때까지 도시를 지나면서 기름을 이전의 기름값을 이용하면 된다.

if (gasStation[i] < toAddGas) toAddGas = gasStation[i]

현재 기름값을 gasStateion이라고 하고, 이전 기름값을 toAddGas라고 할 때, 이전 기름값보다 현재 기름값이 더 쌀 때만 toAddGas를 변경하고 도로의 길이만큼 곱해주면 된다.

 

이 공식은 내가 다른 분의 포스팅으로 공부해서 내가 이해한 것을 바탕으로 정리했다.

https://st-lab.tistory.com/192

[백준] 13305번 : 주유소 - JAVA [자바]

 

 

문제 해결 코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cityCnt = readLine().toInt()
    val road = readLine().split(" ").map { it.toLong() }
    val gasStation = readLine().split(" ").map { it.toLong() }
    var cost = 0L
    var toAddGas = gasStation[0]

    for (i in road.indices) {
        if (gasStation[i] < toAddGas) toAddGas = gasStation[i]

        cost += toAddGas * road[i]
    }

    println(cost)
}

 

문제 풀이

도로의 정보(road)와 리터 당 기름의 가격(gasStation)을 받고, 조건 1에 따라 toAddGas를 변경하고 cost에 toAddGas와 도로의 길이를 곱한 수만큼 누적해서 더해준다.

 

 

문제 해결 과정

도로와 리터당 기름값의 제한이 100억이라서 int로 하면 무조건 범위를 초과하게 된다.

그래서 Long타입으로 해야 하는 것만 조심하면 문제를 쉽게 해결할 수 있다.