[백준] 13305번. 주유소 (JAVA)

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

---

문제

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arrLength = new int[N-1];
        int[] arrPrice = new int[N];

        for(int i = 0; i < N-1; i++){
            arrLength[i] = sc.nextInt();
        }

        for(int i = 0; i < N; i++){
            arrPrice[i] = sc.nextInt();
        }

        long sum = 0, min = arrPrice[0];

        for(int i = 0; i < N - 1; i++){
            if(arrPrice[i] < min){
                min = arrPrice[i];
            }
            sum += (min * arrLength[i]);
        }
        System.out.println(sum);
    }
}

 

문제 이해만 해결된다면 알고리즘은 간단하다. 가격이 최소가 될 때마다 업데이트를 해주면 된다.

 

예시인 가격이 5, 2 ,4, 1인 경우를 예로 생각해보자.

처음엔 이동을 반드시 해줘야 함으로 arrPrice[0]을 설정한다.

이 후 2로 가격이 떨어짐에 따라 업데이트를 해줘야 한다. 가격을 업데이트 한 후에 이동을 진행한다.(여기서 이 전의 가격과 비교 한다는 것이 중요한 포인트이다. 이 후 가격이 더 싸진다는걸 결과적으로 알더라도 기름이 없으면 이동을 할 수 없기 때문이다.)

4의 경우 이전 가격보다 비쌈으로 업데이트를 진행하지 않고 이 전 가격에 거리를 곱해 계산한다.