[백준-그리디] 13305: 주유소 JAVA 자바

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

13305번: 주유소

 

👉 풀이

• 비용이 적은 곳에서 최대한 많이 주유하면 된다.
• 첫번째 도시에서는 적어도 두번째 도시까지 거리만큼은 주유해야한다. 초기 최소가격은 첫번째 도시에서의 주유가격이 된다.
• 두번째 도시부터 도시를 이동해가면서 주유가격이 현재 최소 가격보다 작으면 최소가격을 갱신해가면서, (현재 도시에서 다음 도시까지 거리) * 최소 주유 가격 을 더해나간다.
• N(2 ≤ N ≤ 100,000) 이므로 시간복잡도 O(N)으로 가능

 ex.
도시별 주유가격: 
    8 9 5 4 2 7 1
→ 8 8 5 4 2 2 1

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

public class p13305 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] distances = new long[n-1];
        StringTokenizer stDistance = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n-1; i++){
            distances[i] = Long.parseLong(stDistance.nextToken());
        }

        long[] prices = new long[n];
        StringTokenizer stPrice = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++){
            prices[i] = Long.parseLong(stPrice.nextToken());
        }

        long result = distances[0]*prices[0];
        long cur_price = prices[0];
        for (int i = 1; i < n-1; i ++){
            if(prices[i] < cur_price){
                cur_price = prices[i];
            }
            result += distances[i]*cur_price;
        }

        System.out.println(result);
    }
}

주의: 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 10억 이하의 자연수이다. 리터당 가격은 1 이상 10억 이하의 자연수이므로 int 형 범위(-21억 ~ 21억)를 넘을 수 있다. long형으로 계산해야 한다.