Baekjoon Online Judge

algorithm practice

-問題を逐次解く

16.階調アルゴリズム

特定の状況で成立したグリディアルゴリズムを学びましょう.
Java/Python

ガソリンスタンド

13305号
最低コストで給油して直線道路を走行する問題

この問題は入力した都市の原油価格の降順に、都市ごとの距離を乗じて加算すればいいのです!

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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());
        
		long[] cost = new long[N];    // 비용을 위한 변수
		long[] dist = new long[N-1];    // 거리를 위한 변수
		long sum = 0;
        
		// 거리 입력 
		StringTokenizer 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 min_cost = cost[0];    // 주유 최소 비용
        
		for(int i = 0; i < N - 1; i++){
			if(cost[i] < min_cost){
				min_cost = cost[i];
			}
			sum += (min_cost * dist[i]);
		}
		System.out.println(sum);  
	}
}

Python

import sys
N = int(sys.stdin.readline())
dist = []
cost = []
dist = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))

result = 0
min_cost = cost[0]

for i in range(N - 1):
    if cost[i] < min_cost:
        min_cost = cost[i]
    result += min_cost * dist[i]

print(result)