문제
문제 설명
도시의 개수가 주어지고 각 도시의 기름 가격과 다음 도시까지의 거리가 주어졌을 때 마지막 도시까지 어떻게 기름을 최소비용으로 해서 도달할 수 있는지를 물어보는 문제이다.
일단 이 문제는 Greedy Algorithm을 사용한다. 그리디 알고리즘은 아래와 같은 특성을 갖고 있는 문제들을 해결할 때 사용한다.
-
Greedy Choice Property (탐욕 선택 속성)
한 번 선택하면 이전 단계를 고려하지 않고 각 단계에서의 최선의 선택을 함으로써 문제에 대한 최적의 해결책을 찾는 경우 -
Optimal Substructure (최적 부분 구조)
문제 전체에서의 최적해와 하위 문제의 최적해가 일치하는 경우, 매 순간의 최적해를 고르는 것이 곧 최종 최적해를 고르는 것
문제에서 주어진 예제 입출력을 보면 다음과 같다.
4
2 3 1
5 2 4 1이 문제에서의 비용의 최적화 방법을 생각해보자.
비용을 최소화 하는 방법은 간단하게 리터당 가격이 싼 기름을 넣는 것이다.
첫번째 도시에서 두번째 도시로 가기 위해서는 무조건 기름을 채워야 하므로 5원짜리 기름을 2L 넣어야 하고 10원이다.
두번째 도시에서의 기름값은 2원으로 전 도시보다 싸고 세번째 도시까지 가는 거리 갈만큼 채우면 3L 넣으면 6원이다.
세번째 도시에서 마지막 도시까지 갈때는 거리는 1이지만 비용이 4인데 두번째 도시에서 넣는게 더 싸니깐 두번째 도시에서 4L를 넣는게 이득이다.
그렇게 된다면 첫번째 도시에서 채운 기름 5원 * 2L 과 두번째 도시에서 마지막 도시까지 갈 기름 2원 * 4L 를 더하면 총 18원의 비용이 들게 된다.
최소비용으로 가는 방법은 가격을 입력받은 상태에서 가격이 이전 주유소보다 싸면 넣으면 된다.
현재 입력받은 가격표는 5 2 4 1 인데 이 4를 2로 대체해서 5 2 2 1로 생각하고 주유를 하면 최소 비용으로 마지막 도시까지 갈 수 있다.
구현
거리를 저장할 dist 배열과 기름가격을 저장할 cost 배열을 선언하고 일단 최소금액 minCost를 cost[0]으로 초기화 해준다.
dist = new long[n - 1];
cost = new long[n];
long minCost = cost[0];여기서 타입을 long 으로 선언해준 이유는 문제의 조건에 맞춰서 20억이 넘을 것 같아서 설정해주었다.
그리고 뒤에서 두번째 도시까지 for 문을 반복해주면서 minCost를 초기화 시켜주고 다음 도시까지의 거리만큼 곱해주면 된다.
for (int i = 0; i < n - 1; i++) {
if (cost[i] < minCost) {
minCost = cost[i];
}
sum += (minCost * dist[i]);
}그렇게 하면 다음도시에서도 minCost로 그 다음도시까지 가는거로 계산되어 그냥 최저가 주유소에서 넣었다고 생각할 수 있는 거다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int n;
static long[] dist;
static long[] cost;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
dist = new long[n - 1];
cost = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n - 1; i++) {
dist[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
cost[i] = Integer.parseInt(st.nextToken());
}
long sum = 0;
long minCost = cost[0];
for (int i = 0; i < n - 1; i++) {
if (cost[i] < minCost) {
minCost = cost[i];
}
sum += (minCost * dist[i]);
}
System.out.println(sum);
}
}
