[BAEKJOON] 13305 주유소

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Silver3
• 문제내용:
  • 2번째 줄은 각 도시간의 거리 3번째 줄은 도시별 주우쇼가격이다.
  • 맨 왼쪽에서 출발해서 맨 끝 오른쪽까지 도착하는데 최소한의 비용을 출력해라.

문제풀이

 

 이번문제는 그리디 문제이다. 데이터가 1,000,000,000 이상이고 파이썬이 처리할수 있는 초당 처리할수  연산은 약 천만 정도이다. 그래서 O(n)으로 풀어야 통과가 된다.  그리디에 대한 설명은 아래 사이트에 참조하면된다.

https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘 - 나무위키

 여기서 이전에 가장 싼 주유소 가격이랑 지금 있는 주유소 가격이랑 비교해서 싼 주유소 가격 × 거리로 계산하면된다.

1. 총 비용과 현재 가장 낮은 비용을 선언한다. 총 비용은 처음 거리와 가격을 곱한 값으로 초기화 하고 비용은 첫 도시의 가격으로 선언한다.
2. 지금 도시와 이전에 가장 낮은 비용이랑 비교해서 더 작은 것은 선언한다.
3. 지금 까지 가장 낮은 비용 × 거리를 총 비용에 추가한다.

Code

Python

n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))

# 처음에는 무조건 기름은 넣어야 하기때문에 맨앞에 비용과 거리로 설정한다.
total_cost = roads[0] * costs[0]
cost = costs[0] 
for i in range(1, n-1):
    # 이전 가격이랑 비교해서 싼것 위주로 기름을 넣는다.
    if costs[i] < cost:
        cost = costs[i]
    total_cost += cost * roads[i]
    
print(total_cost)

Java

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());
		int[] roads = new int[N - 1];
		int[] costs = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N - 1; i++) {
			roads[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N ; i++) {
			costs[i] = Integer.parseInt(st.nextToken());
		}
		
		// 처음에는 무조건 기름은 넣어야 하기때문에 맨앞에 비용과 거리로 설정한다.
		long total_cost = (long) roads[0] * costs[0];
		int cost = costs[0];
		for(int i = 1; i < N - 1; i++) {
			// 이전 가격이랑 비교해서 싼것 위주로 기름을 넣는다.
			if (costs[i] < cost) cost = costs[i];
			total_cost += (long) roads[i] * cost;
		}
		System.out.println(total_cost);
	}
}