[ JAVA / 백준 : 13305 ] 주유소

조건

- 처음 출발할 때 기름이 없어서 주유소에서 기름을 넣고 출발

- 1km 마다 1리터의 기름을 사용

- 각 도시마다 주유소의 리터당 가격이 다름

- 왼쪽 도시에서 오른쪽 도시로 이동할때, 최소의 비용을 계산하는 프로그램

---

풀이

- 처음에는 기름을 무조건 넣고 출발해야함

- 2번째 주유소를 들릴 때부터, 이전의 최소값이 현재의 최소값인지 확인!

- 최소값이면 기름을 넣고 이전이 기름값이 더 작으면 이전의 기름값 유지

---

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static int N;
	public static ArrayList<Integer> length = new ArrayList<>();
	public static ArrayList<Integer> price = new ArrayList<>();
	public static long findMin() {
		
		long min = price.get(0);
		long sum = min * length.get(0);
		for(int i = 1; i < N - 1; i++) {
			if(min > price.get(i))
				min = price.get(i);
			sum += min * length.get(i);
		}
		return sum;
	}
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		N = scan.nextInt();
		for(int i = 0; i < N - 1; i++) {
			length.add(scan.nextInt());
		}
		for(int i = 0; i < N; i++) {
			price.add(scan.nextInt());
		}
		System.out.println(findMin());
		scan.close();
	}
}

 

그리디는 무조건 지금 현재에서의 최소, 최대 값을 생각하자!

매일 한문제 씩 푸는것이 요즘은 재밌다!