GasStations

Code

public class GasStations

{

    public double tripCost(int[] dist, int[] price, int _mpg, int tankSize, int tripLength) {

        if(_mpg*tankSize >= tripLength) return 0;

        int N = dist.length, lowerPrice=20001, idx=0;

        double lowestCost=0, tank=tankSize, mpg = _mpg;

        for (int i=0; i < N; i++) {

            for (int j=i+1; j < N; j++) {

                if (dist[j] < dist[i]) {

                    int temp = dist[i];

                    dist[i] = dist[j];

                    dist[j] = temp;

                    temp = price[i];

                    price[i] = price[j];

                    price[j] = temp;

                }

            }

        }

        // 1. Searching the lowest-price station at the starting point

        for (int i=0; i < N; i++) {

            if(dist[i] > tank*mpg) break;

            if(price[i] < lowerPrice) {lowerPrice = price[i]; idx=i;}

        }

        tank -= dist[idx]/mpg;

        LOOP:

        for (int i=idx; i < N; i = idx) {

            // 2. Searching the first lowest-price station

            for (int j=i+1; j<N && dist[j]<=dist[i]+tankSize*mpg; j++) {

                if(price[j] < price[i]) {

                    if(dist[i]+tank*mpg >= dist[j]) tank -= (dist[j]-dist[i])/mpg;

                    else {lowestCost += ((dist[j]-dist[i])/mpg - tank) * price[i]; tank=0;}

                    idx = j;

                    continue LOOP;

                }

            }

            // 3. Going an ending point if possible

            if (dist[i]+tankSize*mpg >= tripLength || i==N-1) {

                if(dist[i]+tank*mpg < tripLength) lowestCost += ((tripLength-dist[i])/mpg - tank) * price[i];

                break;

            }

            // 4. Searching the second lowest-price station

            lowerPrice = price[i+1]; idx = i+1;

            for (int j=i+2; j<N && dist[j]<=dist[i]+tankSize*mpg; j++)

                if(price[j] < lowerPrice) {lowerPrice = price[j]; idx = j;}

            lowestCost += (tankSize-tank) * price[i];

            tank = tankSize - (dist[idx]-dist[i])/mpg;

        }

        return lowestCost;

    }

}

Explanation

1. 출발지점에서는 연료가 가득할 뿐더러 주유소가 아니므로 주유할 필요가 없다. 가장 가격이 싼 주유소를 찾아 가면 된다.
   
   
   (LOOP 시작)
2. 가장 싼 주유소를 찾는다. continue로 넘어가야 계속해서 가격이 제일 싼 주유소를 갈 수 있다.
   tank에 남아 있는 연료로 해당 주유소에 갈 수 있다면 연료만 소비한다. 그게 아니면 해당 주유소까지만 갈 수 있게 연료를 채운다. 즉, 해당 주유소에 도착하면 tank=0 이다.
3. tripLength 거리에 도착가능한 경우 또는 마지막 주유소에 있을 경우에는 연료 주입 후 주행을 끝낸다.
4. 도달 가능한 거리가 아니면 2번째로 싼 주유소를 찾아 간다. (why? 2번을 통해 현재 있는 주유소보다 가장 싼 주유소가 없다는 걸 알 수 있다.)