[13305번] 주유소 ( 탐욕법, 내림차순 )

리터당 기름 값이 '내림차순'일 경우에 주유하면 된다.

즉, 5 2 4 1 에서 5 다음 2는 내림차순 이므로 5와 2가 선택되고, 그 다음의 수 4는 내림차순이 아니기 때문에 마지막에 선택되었던 내림차순 수인 2로 계산되어야 한다. (1은 더이상 갈 도로가 없기 때문에 제외됨)

즉, 5 2 2 1 이 되는 것이고, 각 도로별 길이는 2, 3, 1 이었으므로, (5 2) + (2 3) + (2 * 1) = 18 로 최소비용이 된다.

✅ 코드

오름차순이 시작 될 때의 값을 그 전의 값으로만 바꿔주면 되는 문제였다.

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

public class Main {
	static int d[];
	static int p[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());

		d = new int[n - 1];
		p = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n - 1; i++) {
			d[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			p[i] = Integer.parseInt(st.nextToken());
		}

		int sum = 0;
		int end = n - 1;

		for (int i = 0; i < end; i++) {
			for (int j = i + 1; j < end; j++) {
				if (p[i] <= p[j]) {
					p[j] = p[i];
				}
			}
		}

		for (int i = 0; i < end; i++) {
			sum += (p[i] * d[i]);
		}

		System.out.println(sum);
	}
}