13305-주유소

<문제>

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

13305번: 주유소

<풀이>

포인트 : 주유소의 가격이 가장 낮은 도시에서 최대한 먼거리를 이동할 경우 이동비용이 최소가 된다!

주유소 가격이 저장된 배열에서 가장 낮은 가격을 직접 찾는 방법으로 접근했지만 이렇게 접근할 경우

서브태스크의 2번문항을 만족하지 못해 높은 점수를 받지 못한다.

따라서 왼쪽에서부터 반복문으로 출발하면서 기존 가격보다 낮은 가격이 나올경우 가장 낮은 가격을 갱신해나가는 식으로 접근해야한다. 

 

-파이썬 코드-

#N: 도시의 개수
#각 도시를 연결하는 도로의 길이(최대 10,000)
#주유소 리터당 가격(최대 10,000)
#1리터당 1km
n = int(input())
city_dist = list(map(int,input().split()))
gas_price = list(map(int,input().split()))
price = city_dist[0]*gas_price[0]
min_price = gas_price[0]
dist = 0
for i in range(1,len(city_dist)):
    if gas_price[i]<min_price:
        price+=min_price*dist
        min_price = gas_price[i]
        dist = city_dist[i]
    else:
        dist+=city_dist[i]
    if i==n-2:
        price+=dist*min_price

print(price)
#풀이 2 : 거리를 더해주다가 마지막 도시로 넘어갈때 계산하는것이 아닌 각 도시마다 비용을 계산하는 방식이다.
# for i in range(n-1):
#     if gas_price[i]<min_price:
#         min_price = gas_price[i]
#     price+=min_price*city_dist[i]

-자바 코드-

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long [] roads = new long[n-1];
        long [] cost = new long[n];
        long price = 0;
        for(int i = 0;i<roads.length;i++){
            roads[i] = sc.nextLong();
        }
        for(int i = 0;i<cost.length;i++){
            cost[i] = sc.nextLong();
        }
        
        
        long min_price = cost[0];
        for(int i=0;i<=n-2;i++){
            if (cost[i]<min_price) min_price = cost[i];
            price+=min_price*roads[i];
        }
        System.out.println(price);

    }
}

※주의점

1)입력값의 범위 때문에 int가 아닌 long으로 선언해야한다.

2)위 파이썬 코드의 풀이2방법으로 해야 런타임 에러가 안난다.