[백준(Baekjoon)][자바(java)] 13305 : 주유소 / 그리디 알고리즘

 

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 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int n = Integer.parseInt( br.readLine() ), i, j;
		int d[] = new int[n-1], c[] = new int[n];
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n-1; i++ )
			d[i] = Integer.parseInt( st.nextToken() );
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			c[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		long c_sum = 0, dd;
		for( i = 0; i < n-1; ) {
			dd = 0;
			for( j = i; j < n-1; j++ ) {
				if( c[i] > c[j] )
					break;
				dd += d[j];
			}
			c_sum += dd * (long)c[i];
			i = j;
		}
		System.out.println( c_sum );
        
	}
}

 

*  그리디

-  현재 지점에서의 기름값이 다음 지점의 기름값보다 클 때까지 거리를 더한 후
   '(리터당)기름값 x 더한 거리'를 더해가며 총 비용을 구한다