[알고리즘] 백준 13305 주유소 -그리디- 자바 코틀린

 

www.acmicpc.net/problem/13305

13305번: 주유소

 

 

 

 

 

백준 그리디 단계별풀기에서 마지막 문제를 안풀어서 이번에 풀어봤습니다. 

 

문제에 대해 간략히 설명하면, 기름값이 다른 도시들이 있고 각 도시는 일렬로 다른거리로 연결되어 있습니다.

도시에 도착했을때 기름*km수 만큼 기름을 채울 수 있다.  마지막도시까지 가는데 필요한 최소 기름값을 출력하면 됩니다.

 

풀이 방법은 기름값이 이전 도시보다 더 낮은 경우 더 낮은 기름값으로 다음 도시까지의 거리만큼 기름을 채워주면 됩니다. 만약 지금 도시가 이전 도시들에서의 최소 기름값보다 더 적으면 최소 기름값으로 채워주면 됩니다. 

풀이를 보면 이해하기 쉬울거라 생각합니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

class Main {
    private static int N; // 도시의 개수
    private static long[] distances; // 거리
    private static long[] costs; // 비용
    private static long sum = 0; // 총 비용 (답)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        distances = new long[N - 1];
        costs = new long[N];
        for (int i = 0; i < N - 1; i++) {
            distances[i] = sc.nextLong();
        }
        for (int i = 0; i < N; i++) {
            costs[i] = sc.nextLong();
        }
        //첫번째 도시 출발지점 초기화
        long minCost = costs[0];
        sum = minCost * distances[0];
        //두번째도시 ~~ 마지막도시
        for (int i = 1; i < N - 1; i++) {
            if (costs[i] < minCost) { //최소 기름값 업데이트
                minCost = costs[i];
            }
            sum += minCost * distances[i];
        }
        System.out.println(sum);
    }
}

 

 

[Kotlin]

import java.util.*

private var N // 도시의 개수
        = 0
private lateinit var distances // 거리
        : LongArray
private lateinit var costs // 비용
        : LongArray
private var sum: Long = 0 // 총 비용 (답)


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    distances = LongArray(N - 1)
    costs = LongArray(N)
    for (i in 0 until N - 1) {
        distances[i] = sc.nextLong()
    }
    for (i in 0 until N) {
        costs[i] = sc.nextLong()
    }
    //첫번째 도시 출발지점 초기화
    var minCost = costs[0]
    sum = minCost * distances[0]
    //두번째도시 ~~ 마지막도시
    for (i in 1 until N - 1) {
        if (costs[i] < minCost) { //최소 기름값 업데이트
            minCost = costs[i]
        }
        sum += minCost * distances[i]
    }
    println(sum)
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!