[백준] 13305 주유소 - Greedy / Java

• 문제 링크

13305번: 주유소

 

• 풀이 과정

우선 맨 처음 주유소는 다음 주유소로 이동하기 위해 필연적으로 이용해야 하며

마지막 주유소는 도착 지점이므로 계산에 포함되지 않는다.

 

각 주유소에 도달했을 때 해당 주유소의 가격이 다음 주유소의 가격보다 저렴하다면

다음 주유소에서 주유할 분량을 미리 주유하여 비용을 최소화하며

이는 현재 상황에서 최선의 수를 선택하는 그리디 알고리즘의 기본 원리에 부합한다.

 

첫번째 입력에서 이와 같은 규칙을 적용 시 5 2 4 1 -> 5 2 2 1 로 변경되고

각각에 마지막 주유소를 제외한 구간별 거리를 곱하여 (5 * 2) + (2 * 3) + (2 * 1) = 18 으로 최소 비용이 구해진다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		long[] dist = new long[n - 1];
		long[] cost = new long[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n - 1; i++)
			dist[i] = Long.parseLong(st.nextToken());

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			cost[i] = Long.parseLong(st.nextToken());

		long sum = 0;
		long min = cost[0];
		for (int i = 0; i < n - 1; i++) {
			if (cost[i] < min)
				min = cost[i];

			sum += min * dist[i];
		}

		bw.write(sum + "\n");
		bw.flush();
	}

}