백준 13305 주유소 Java 풀이

문제

이런류의 문제는 설명이 장황해서 실제 코딩테스트에서 마주치면 당황할 수 있지만, 잘 읽어보면 쉬운 문제이다.

 

N 개의 도시를 직선 방향으로 이동할껀데, 기름이 0인 차를 타고 시작한다.

각 도시간 거리와 각 도시의 리터랑 가격이 주어진다.

1리터랑 거리 1씩 이동할 수 있다.

이때 지불하는 최소한의 금액을 구하여라

 

문제 출처 : https://www.acmicpc.net/problem/13305

접근

첫번째 도시에서는 다음 도시까지 가기위해서는 어쩔수 없이 distance[0] * oilPrice[0] 만큼 값일 치뤄야한다.
만약 oilPrice[0] < oilPrice[1] 라면 (distance[0] + distance[1]) * oilPrice[0] 만큼 값을 치루고 간다.
위와 같이 다음 도시의 기름값이 지금 도시의 기름값보다 비싸다면, 지금 도시에서 해당 거리만큼을 채워넣는다.

 

이러한 접근방법을 일반화하면되고, 순회횟수는 각도시간 거리가 N-1 까지만 주어지고 N 번째 도시의 주유소에서 주유하는것은 최소비용일 수 없기 때문에 은 N-1 까지만 하면된다. 

 

풀이

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));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine()); // number of cities
        int[] distance = new int[N-1]; // distance between cities [i, i +1]
        int[] oilPrice = new int[N]; // oil price per liter at city of i index

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N-1; i++) {
            distance[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            oilPrice[i] = Integer.parseInt(st.nextToken());
        }

        long totalPrice = 0;
        int minOilPrice = oilPrice[0];
        for (int i = 0; i < N-1; i++) {
            minOilPrice = Math.min(oilPrice[i], minOilPrice);
            totalPrice += (long) minOilPrice * distance[i];
        }
        System.out.println(totalPrice);
    }
}