[백준 / Java] 13305번: 주유소 (실버3)

문제 풀이 날짜: 2023.05.16
포스트 작성일: 2023.05.18

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 13305번: 주유소 (실버3) (문제 링크)

 

키워드

그리디

 

풀이 접근법

• 첫 번째 도시에서는 가진 기름이 없기 때문에 무조건 주유를 해야 한다.
• 마지막 도시에 도착하면 주유할 필요가 없기 때문에 마지막 도시의 기름값은 의미가 없다.
• 따라서 중간의 어느 도시에서 주유할 지를 선택하는 게 중요하다.
• 2 ≤ N ≤ 100,000 이기 때문에 O(N²) 시간을 넘지 않는 방식으로 해결해야 한다.
• 각 도시에서 주유를 할지 말지의 여부를 어떻게 결정할까?
  
  • 다음 도시의 기름값(cost[i])이 현재 머무르고 있는 도시의 기름값(currCost)보다 크다면 현재 도시에서 다음 도시까지 쓸 기름을 주유한다.
  • 또 그 다음 도시의 기름값을 확인하고, 현재 도시의 기름값과 비교한다. 현재 도시보다 싼 도시가 나올 때까지 누적시킨다. 더 싼 도시를 발견하면 그곳으로 이동해서(currCost = cost[i] 할당) 주유한다. 마지막 도시까지 확인하면 종료한다.
  • 즉, 주유해야 하는 리터 수는 일정하므로 (전체 dist만큼) dist[i]만큼의 기름을 어느 주유소에서 주유할 지를 반복문으로 currCost와 비교하면서 찾으면 된다. (currCost : 역대 방문한 주유소 중 가장 낮았던 주유비를 기록)

 

코드

import java.io.*;
import java.util.*;

public class Q13305 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		long[] cost = new long[N];
		long[] dist = new long[N - 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");;
		for(int i = 0; i < N - 1; i++) {
			dist[i] = Long.parseLong(st.nextToken()); 
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			cost[i] = Long.parseLong(st.nextToken()); 
		}
		
		long sum = 0;
		long currCost = cost[0];
		sum += currCost * dist[0];
		for(int i = 1; i < N - 1; i++) {
			if(currCost > cost[i]) { //더 싼값에 주유할 수 있다면
				currCost = cost[i];
			}
			sum += currCost * dist[i];
		}
		
		System.out.print(sum);
	}

}

---

매 순간마다 최선의 선택을 한다는 그리디 알고리즘인 만큼, 매 순간마다 가장 비용이 작은 주유소를 택하는 발상이 중요한 문제였다. 필요한 비용을 계속 누적시켜야 하는 문제이고, 입력으로 주어지는 가격 또한 큰 편이다. 오버플로우가 일어나지 않도록 무언가를 누적시켜야 하는 변수를 long 타입으로 선언해주었다.  

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day3/Q13305.java