백준 13305 - 주유소 (Java)

 

문제 개요

 

문제 개요

 

예제 입출력

 

---

 

풀이

 

입력 값이 아래와 같이 주어졌을 때 기름 값으로 드는 비용의 최소 비용을 구해야 한다.

 

• 각 도시에서의 기름 값
• 도시와 도시 사이의 거리
• 경유해야 할 도시의 순서

 

문제에도 나와있지만 기름을 구입하는 시기에 따라 최종 목적지까지 도착했을 때 소비한 총액수가 달라지므로 그리디 알고리즘으로 풀어야 한다.

 

문제를 풀기위한 내 생각은 다음과 같다.

 

1. 각 도시에서의 기름 값 정보, 도시와 도시 사이의 거리를 차례대로 입력받는다.
   • 차례대로 입력받은 정보가 경유 순서가 된다.
2. 첫 도시부터 시작해서 현재 도시의 기름 값과 다음 도시의 기름 값을 비교한다.
3. 반복하는 과정에서 만약 현재 도시의 기름 값이 다음 도시보다 저렴한 경우에는 현재 도시에서 기름을 더 사고 가는 것이 유리하므로 기름을 더 구매한다.
   • 현재 도시에서 다음 도시와 그 다음 도시까지의 거리만큼의 기름을 더 구입한다.
4. 만약 현재 도시의 기름 값이 다음 도시보다 비싼 경우에는 현재 도시에서 다음 도시까지 이동하는 거리만큼의 기름만 구매한다.
5. 마지막 도시에 도착하면 종료되기 때문에 마지막 도시는 비교하지 않고 반복을 종료한다.
6. 이동하면서 구매한 총 금액을 출력한다. 

 

---

 

코드

 

import java.io.*;

public class Main {
    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        Long[] len = new Long[count-1];
        Long[] oil = new Long[count];

        String[] items = br.readLine().split(" ");
        for (int i=0 ; i<count-1 ; i++)
            len[i] = Long.parseLong(items[i]);

        items = br.readLine().split(" ");
        for (int i=0 ; i<count ; i++)
            oil[i] = Long.parseLong(items[i]);

        long min = oil[0];
        long total = 0;
        for (int i=0 ; i<count-1 ; i++) {
            if (oil[i] < min)
                min = oil[i];
            total += min * len[i];
        }

        System.out.println(total);
        return;
    }
}

 

코드 리뷰를 하기 전에 주의할 점이 있다.

 

도시와 도시 사이의 거리, 각 도시에서의 기름 값은 숫자 형태로 저장해야 후에 비교하기에 용이하기 때문에 int형으로 입력을 받으려고 했지만 그렇게 하면 안 된다.

 

왜냐면 문제 하단의 조건에서 도시와 도시 사이 거리와 기름 값의 범위를 0~1,000,000,000로 제한했기 때문이다.

Java에서 int형의 범위는 -2,147,483,648 ~ 2,147,483,647이다.

 

즉, 만약 기름 값이 1,000,000,000인데 거리가 3을 넘어서는 순간 오버플로우 에러가 발생하는 것이다.

따라서 여기서는 이를 해결하기 위해 Long 자료형을 사용하였다.

 

 

코드 리뷰

 

1. 총도시의 수를 count에 저장한다.
2. count를 기반으로 도시 사이의 거리를 담을 long형 배열 len을, 각 도시에서의 기름 값을 저장할 long형 배열 oil을 선언 후 for문을 통해 값을 넣어준다.
   • 문제에서 첫 줄에 총 도시의 수를, 그다음 줄에 각 도시 사이의 거리를, 마지막 줄에 각 도시에서의 기름 값을 입력 값으로 지정했다.
3. 첫 도시에서 두 번째 도시까지 이동할 때는 기름을 구매할 선택권이 없기 때문에 초기 값인 변수 min에 oil[0]을 저장하고, 총 사용한 비용이 저장될 변수 total을 생성한다.
   • 변수 이름이 min인 이유는 첫 값은 oil[0]이지만 작은 값이 나온다면 해당 값으로 변경할 것이기 때문에 점점 작아진다는 의미로 작명했다.
   • 실제로 반복문이 종료된 이후에 min에 담겨있는 값은 전체 도시 중 기름 값이 가장 작은 도시의 기름 값이 될 것이다.
4. for문으로 oil[i]와 min을 반복하여 비교하도록 만들고, 만약 min보다 oil[i]이 더 작은 경우에 min에 oil[i]을 넣어준다.
5. total에 min(기름 값) * len[i](다음 도시까지 이동 거리)을 누적하여 저장한다.
   • 이론상으론 현재 루프는 현재 도시를 의미한다.
   • 현재 도시에서 다음 도시로 이동하려고 할 때 기름 값을 결정짓는 기준이 바로 min과 oil[i]를 비교하는 것이다.
   • 만약 min이 더 작았다고 하면 [기름 값이 min이었던 도시]에서 [현재 도시에서 다음 도시로 가는 거리]만큼의 기름 값을 더 사는 것이다.
6. 반복문이 종료되었을 때 total을 출력해준다.

 

---

 

제출 결과

 

제출 결과

 

4달 전과 비교하면 조금 더 간결하고 효율적으로 작성이 된 것 같다.

 

문제를 푸는 시간도 이전에 풀었던 적이 있어서인지 상대적으로 적은 시간 안에 푼 것 같다.