[BOJ 그리디] 주유소 13305.JAVA

문제 링크 : https://www.acmicpc.net/problem/13305
문제 등급 : Silver IV

13305번: 주유소

문제 해결 로직

1. 리터당 가격을 기준으로 반복문을 돌린다.
2. 이전 리터의 가격과 현재 리터의 가격을 비교하여 작은 값을 기록한다.
3. 작은 값으로 거리와 곱해 주유 비용을 계산한다.

위의 로직을 보면 매우 간단하다.

하지만 처음 문제를 풀었을 때 17점을 받았었다.

 

간단히 공유하자면

1. 이전 도시에서 주유한 주유비와 현재 도시의 주유 비와 앞으로 갈 전체 거리를 계산하여 기록하였다.

2. 이전의 주유비와 비교하여 작은 값을 기록하였다.

3. 앞으로 간 거리만큼 전체 거리에서 빼주고 이전 도시에서 주유한 주유비를 기록하였다.

long tot = Integer.MAX_VALUE, stat = 0;

for(int i = 0; i < dis.length; i++) {
  long d = dis[i];
  long a = Long.parseLong(amounts[i]);
  tot = Math.min(tot, stat + (a * totDis));
  totDis -= d;
  stat += (a * d);
}

위의 1~3번을 반복하면 가장 작은 값의 주유비가 나온다 하지만 값이 너무 커질 수 있다.

BigInteger로 구현해도 17점이였다. 

차이점은 틀린 로직에서 불필요한 계산이 들어가는것 밖에 없었는데 17점을 받았다.

메모리나 시간상의 문제도 없었다.

왜 틀렸는지 의문이지만 해결된 로직이 더 간결하긴하다...

 

아래와 같이 해결 로직의 소스를 공유합니다.

public class 주유소 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        br.readLine();

        String[] dis = br.readLine().split(" ");
        String[] amounts = br.readLine().split(" ");

        long min = Long.parseLong(amounts[0]), tot = 0;
        
        for (int i = 0; i < dis.length; i++) {
            long d = Long.parseLong(dis[i]);
            long a = Long.parseLong(amounts[i]);

            if(a < min) min = a;

            tot += (min * d);
        }

        System.out.println(tot);
    }
}