[BOJ 13305] 주유소 (Java)

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

13305번: 주유소

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

public class Main_BOJ_13305 {
	static int N;
	static long[] dist;
	static long[] prices;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		prices=new long[N];
		dist=new long[N-1];
		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++) {
			prices[i]=Long.parseLong(st.nextToken());
		}
		long min=Long.MAX_VALUE;
		long sum=0;
		for (int i=0; i<N-1; i++) {
			if (prices[i]<min) {	//최소값 발견 시 그걸로 사기
				min=prices[i];
			}
			sum+=(min*dist[i]);
		}
		System.out.println(sum);
	}

}

그리디 알고리즘.

 

최소값 발견 시 그걸로 갱신하고, 그것보다 작은 값을 발견할때까지 쭉 그걸로 구매하는 방식이다.

범위 설정에 유의하자.