S13305. 주유소

문제

제출 코드

• 사용 알고리즘 : 그리디

시작점에서 도착점까지, 거쳐가는 주유소들에서 기름을 최소비용으로 채워 도착점까지 가는 문제.

기름을 언제 채울때 최소가 되는지를 파악하면 간단하게 풀리는 문제이다.

현재 위치보다 더 싸게 파는 주유소가 나올때까지 갈 수 있을정도로 기름을 채우는 방식으로 생각하면 된다.

주어진 수의 범위를 생각하지 못하고 int범위로 문제를 풀었다가 한번 틀렸다.

package silver;

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

public class S13305_gasStation {

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] street = new int[N];
		for(int i=1; i<N; i++) street[i] = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int min = Integer.parseInt(st.nextToken()); // 거쳐온 주유소 중 최소 기름 비용
		long cnt=0, result=0; // cnt = 채워야 할 기름 양, result = 최소기름비용 합계

		for(int i=1; i<N; i++) {
			int now = Integer.parseInt(st.nextToken());
			cnt += street[i];

			if(now < min) {
				result += cnt * min;
				min = now;
				cnt = 0;
			}
		}

		if(cnt!=0) result += cnt * min;

		System.out.println(result);
	}

}