백준 13305번: 주유소[JAVA]

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

13305번: 주유소

 

 

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        BigInteger[] dist = new BigInteger[N - 1]; // 거리 배열
        BigInteger[] cost = new BigInteger[N]; // 비용 배열

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            dist[i] = new BigInteger(st.nextToken()); // 거리 배열 입력
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            cost[i] = new BigInteger(st.nextToken()); // 비용 배열 입력
        }

        BigInteger total = BigInteger.ZERO; // 총 주유 비용
        BigInteger min = cost[0]; // 가장 싼 기름 값
        for (int i = 0; i < N-1; i++) {
            if (min.compareTo(cost[i]) > 0) { // 왼쪽값이 오른쪽 값보다 크면 1, 같으면 0, 작으면 -1
                min = cost[i]; // 현재 가장 싼 기름 값 보다 더 싼 곳이 있을경우 갱신
            }
            total = total.add(min.multiply(dist[i])); // 가야할 거리 * 현재 가장 싼 기름값
        }
        System.out.println(total); // 출력
    }
}

 

[설명]

이 문제는 그리디 알고리즘 문제이다. 처음 문제를 봤을때는 쉬워 보이지만 아이디어가 잘 생각나지 않아 구글링을해 다른사람들의 아이디어를 참고했다. 

기본적인 아이디어는 현재 알고있는 기름값 보다 더 싼 비용의 기름값을 만날때 까지 충전해 길을 가는것이다.

예를들면 노드가 8 9 9 5 6 2 4 4 5 1 1 이런식으로 되어있다면 시작지점에서 가장 싼 기름값은 1리터당 8원이다. 그다음 노드의 비용응 9이므로 그다음 싼 기름값인 지점인 5노드까지 8원 인 노드에서 한번에 충전해서 가는것이다. 그 다음 더 싼 비용의 노드를 만나면 그때 가장 싼 기름값을 갱신시켜 그보다 싼 비용의 노드를 만날때 까지 가는것이다. 

쉽게 보자면 8 9 9 5 6 2 4 4 5 1 1 이 아닌 8 8 8 5 5 2 2 2 2 1 1 이렇게 볼 수 있다. 코드에 주석이 달려 있으니 확인해보면 좋다.

중요한 점이 하나 더 있다. 바로 BigInteger를 사용하는 것이다. 이 문제는 매우 큰 수를 사용하기 때문에 int로는 정답을 도출해 낼 수 없다.

BigInteger total 에 0이 담겨야한다. 이 때 total = 0이 아닌 BigInteger.ZERO 로 0을 담을 수 있다.

BigInteger 끼리의 대수 비교를 할 때 단순 부등호를 활용해 비교하는것이 아닌. BigInteger1.compareTo(BigInteger2) 를 활용해야 한다. 이때 왼쪽에 적은 BigInteger1이 오른쪽에 적은 BigInteger보다 크다면 1, 같으면 0, 작다면 -1이 출력된다.

그래서 현재 알고있는 가장 싼 기름값 보다 새로 알게된 기름값이 더 싸다면 1이 출력되 if문이 true가 되어 가장 싼 기름값을 갱신해준다.

마지막에 가야할거리*기름값을 계산할때 total = total + ( min * dist[i] )가 아닌 BigInteger.add(BigInteger.multiply(BigInteger) 형식으로 계산을 해주어야 한다.

결론적으로 이 문제는 그리디 + BigInteger의 활용하는 문제였다.