[백준] 13305번 : 주유소 - JAVA [자바]

 
www.acmicpc.net/problem/13305

13305번: 주유소

 

---

• 문제

 

 

 

 

설명이 조금 복잡해보이나 원리만 이해하면 정말 쉬운 문제다.

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

문제 설명이 길어서 그렇지 내용 자체가 어려운 문제는 아니니 먼저 문제부터 이해하고 넘어가보자.

 

먼저 N개의 도시가 있고, 각 도시를 잇는 N-1개의 도로가 있다. 그리고 각 도시에는 주유소의 리터당 가격이 써져 있고, 각 도로에는 거리가 적혀져 있다. (1km당 1L 기름을 사용함)

 

문제에 있는 예시를 보면 이렇다.

 

 

 

 

즉, 도시 A부터 D까지 도착하는데 총 비용을 최소화 하는 방법을 생각해야 한다는 것이다.

 

 

비용을 최소화 하는 방법은 뭘까? 간단하다. '리터당 가격이 싼 기름을 넣는 것' 이다.

 

한 번 차근차근 풀어보자.

도시 A에서는 B로 가기 위해서 무조건 기름을 채워야 하므로 5원짜리 기름을 2L 넣어야 한다. 즉, 10원이 든다.

 

도시 B에서 C로 가는 것은 어떨까?

도시 B는 도시 A보다 기름값이 싸다. 굳이 도시 A에서 C까지 가야하는 기름을 채울 필요 없이, A에서는 2km에 해당하는 양(2L)을 채우고, 도시 B에서 한 번 더 주유해서 도시 C까지 가는데 필요한 기름을 채우면 된다. B에서 C까지 가는데 필요한 비용은 3L * 2원이므로 6원이 필요하다.

이는 A에서 C까지 가는데 필요한 비용을 정리하자면 (2L * 5원) + (3L * 2원) 이다.

 

마지막으로 C에서 D까지 가는데 필요한 비용은 어떻게 될까.

도시 C의 리터당 가격은 4원으로 여기서 채우는 것보다 이전의 도시. 즉, B도시에서 D까지의 거리만큼 기름을 채우는 것이 훨씬 싸다.

 

즉, B주유소에서 D도시까지 가기 위한 기름을 채우는 것이니, 4L * 2원을 B주유소에서 지불하게 되는 것이다.

 

정리하자면 A도시 주유소에서 2km를 가기 위해 2L를 채워 2 * 5 = 10원의 비용이 들고, B도시의 주유소에서 D까지 4km를 가기위해 4L를 채워 4L * 2 = 8원의 비용이 든다.

 

총 합하면 18원의 비용이 드는 것이다.

 

 

이렇게 문제풀이 하면서 눈치를 채신 분도 있겠지만, 최소비용으로 가는 방법은 간단하다.

리터당 기름 값이 '내림차순'일 경우에 주유하면 된다.

 

즉, 5 2 4 1 에서 5 다음 2는 내림차순 이므로 5와 2가 선택되고, 그 다음의 수 4는 내림차순이 아니기 때문에 마지막에 선택되었던 내림차순 수인 2로 계산되어야 한다. (1은 더이상 갈 도로가 없기 때문에 제외됨)

 

즉, 5 2 2 1 이 되는 것이고, 각 도로별 길이는 2, 3, 1 이었으므로, (5 * 2) + (2 * 3) + (2 * 1) = 18 로 최소비용이 된다.

 

 

 

예로들어 도시 7개의 각 주유소별 리터당 가격이 (8, 9, 5, 4, 2, 7, 1) 이고, 각 도시별 거리가 (3, 4, 2, 2, 4, 5) 라고 해보자.

그럼 일단 주유소별 리터당 가격을 내림차순으로 하면 이렇다.

 

8, 9, 5, 4, 2, 7, 1  → 8, 8, 5, 4, 2, 2, 1

 

그리고 위 수에 각 도시별 거리를 곱해주면 이렇다.

(8 * 3) + (8 * 4) + (5 * 2) + (4 * 2) + (2 * 4) + (2 * 5) = 92

 

즉, 최소비용이 92다.

 

감이 오시는가? 결국 최종적으로 우리가 해야할 것은 입력받은 도시별 기름 가격을 내림차순으로 만들어 각 도시별 거리를 곱하여 더해주면 되는 것이다.

 

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려한다.

 

1 . Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		long[] dist = new long[N - 1];	// 거리
		long[] cost = new long[N];	// 비용 
		
		// 거리 입력 
		for(int i = 0; i < N - 1; i++) {
			dist[i] = in.nextLong();
		}
		
		// 리터당 기름값 입력
		for(int i = 0; i < N; i++) {
			cost[i] = in.nextLong();
		}
		
		long sum = 0;
		long minCost = cost[0];	// 이전 까지의 과정 중 주유 최소 비용 

		for(int i = 0; i < N - 1; i++) {
			
			/*
			 *  현재 주유소가 이전 주유소의 기름값보다 쌀 경우
			 *  minCost를 갱신해준다. 
			 */
			if(cost[i] < minCost) {
				minCost = cost[i];
			}
			
			sum += (minCost * dist[i]);	// 총 비용 누적 합
		}
		
		System.out.println(sum);
		
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

매우 간단한 알고리즘임을 볼 수 있다. 참고로 sum의 경우 int형 데이터 범위를 넘기에 충분히 큰 데이터들이 들어오니 반드시 long형으로 해주어야 한다.

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[] dist = new long[N - 1];	// 거리
		long[] cost = new long[N];	// 비용 
		
		// 거리 입력 
		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 minCost = cost[0];	// 이전 까지의 과정 중 주유 최소 비용 

		for(int i = 0; i < N - 1; i++) {
			
			/*
			 *  현재 주유소가 이전 주유소의 기름값보다 쌀 경우
			 *  minCost를 갱신해준다. 
			 */
			if(cost[i] < minCost) {
				minCost = cost[i];
			}
			
			sum += (minCost * dist[i]);
		}
		
		System.out.println(sum);
		
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 25211454  -  방법 2 : BufferedReader

채점 번호 : 25211456  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

그리디 문제는 의외로 상식선에서 풀 수 있어서 그리 어렵지는 않을 것이다. 물론 그리디 알고리즘이라고 명시되어 있기 때문인 것도 있다. 그러니 많은 유형의 문제들을 익혀가면서 꼭 어떤 문제를 보고 어떤 알고리즘을 적용하면 좋을지를 판단할 수 있는 직감을 기르는 것도 매우 좋은 방법일 듯 하다.