백준 13305 주유소

Algorithm

백준 13305 주유소

dalooong 2023. 7. 10. 09:43

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

💡 움직이면서 주유하는 시뮬레이션이 아닌, 어떻게 주유하면 최소비용으로 이동할지를 판단하는 문제입니다. 출발하고자 하는 도시보다 기름값이 더 싼 도시가 나올때까지만 이동하기를 반복하는 탐욕적 방법으로 답을 구할 수 있습니다.

주의할점은 입력 조건의 크기가 매우 크기 때문에, int 자료형을 사용하면 서브테스크 3번을 틀리게됩니다. 이 경우 long 을 사용하면 문제없이 답을 구할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public long solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long cityCount = Integer.parseInt(reader.readLine());
        StringTokenizer cityDistToken = new StringTokenizer(reader.readLine());
        long[] cityDistance = new long[(int) (cityCount - 1)];
        for (int i = 0; i < cityCount - 1; i++) {
            cityDistance[i] = Integer.parseInt(cityDistToken.nextToken());
        }

        StringTokenizer cityFuelToken = new StringTokenizer(reader.readLine());
        long[] cityFuel = new long[(int) cityCount];
        for (int i = 0; i < cityCount; i++) {
            cityFuel[i] = Integer.parseInt(cityFuelToken.nextToken());
        }

        long currentMin = Integer.MAX_VALUE;
        long needToGo = 0;
        long totalPrice = 0;
        for (int i = 0; i < cityCount - 1; i++) {
            // 현재 도시의 기름값이 여태까지 중 제일 싸다
            if (cityFuel[i] < currentMin) {
                // 여태까지 온 거리만큼 그 전까지 싼 도시에서 넣자.
                totalPrice += currentMin * needToGo;
                // 이제 여기가 제일 싸다.
                currentMin = cityFuel[i];
                // 여기서부터 출발해서 가야되는 거리
                needToGo = cityDistance[i];
            }
            // 예전이 더 싸다.
            else {
                // 여기서 더 가야된다.
                needToGo += cityDistance[i];
            }
        }

        return totalPrice + needToGo * currentMin;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new Main().solution());
    }
}