BOJ_13305 : 주유소

👉 문제링크

13305번: 주유소

---

---

🔸 문제 분석 🔸

• n개의 마을이 일렬로 주어지며 n-1개의 도로가 있다.
  • 마을마다 1L당 기름값이 주어지며, 도로 1km당 기름 1L가 필요하다.
  • 최종 기름값의 최소값을 출력한다.
• 전형적인 그리디 알고리즘 문제이다.
  • 가장 가성비 좋게 기름을 구입하기 위해서, 최종 도시에서 거꾸로 빼는 방식으로 계산한다.
• 도로의 길이와 도시 별 기름값의 최대 값이 10억이므로 long형을 사용한다.

🔸 코드 🔸

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));
        int n = Integer.parseInt(br.readLine());
        long[] road = new long[n - 1];
        long[] city = new long[n];
        int min_index = 0;
        long min = 1000000001;
        long r = 0;
        long answer = 0;

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            city[i] = Integer.parseInt(st.nextToken());
            if (min > city[i] && i < n - 1) {
                min = city[i];
                min_index = i;
            }
        }

        n--;

        while (r > 0) {
            long len = 0;
            for (int i = n-1; i >= min_index; i--) {
                len += road[i];
            }

            answer += min * len;
            r -= len;

            n = min_index;
            min = 1000000001;
            for (int i = 0; i < n; i++) {
                if (city[i] < min) {
                    min_index = i;
                    min = city[i];
                }
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• n-1개의 도로 길이와 n개의 도시 별 기름값을 입력받는다.
• 남은 도로 길이 r이 0이 될 때까지 계산을 반복한다.
  • 현재 위치부터 기름값이 최소인 도시까지의 거리를 r에서 뺀다.
  • 구한 거리 x 기름 값을 출력 변수 answer에 누적한다.
  • 현재 위치를 이동하고, 기름값이 최소인 도시를 찾는다.

---

🔸 end 🔸

• 오랜만에 코테 문제를 풀어서 그런지 감이 안잡혀서 태그를 보고 그리디 알고리즘 힌트를 얻어 풀었다.