https://www.acmicpc.net/problem/13305
문제
> 어떤 나라에 N개의 도시가 있다.
> 이 도시들은 일직선 도로 위에 있다.
> 편의상 일직선을 수평 방향으로 두자.
> 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다.
> 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다.
> 도로 길이의 단위는 km를 사용한다.
> 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다.
> 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다.
> 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다.
> 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다.
> 가격의 단위는 원을 사용한다.
> 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자.
> 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다.
> 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.
> 제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다.
> 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원)
다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원)
다음 도시에서 1리터의 기름을 넣어(1×4 = 4원)
제일 오른쪽 도시로 이동하면, 총 비용은 20원이다.
> 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원)
다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원)
제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.
> 각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아
제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.접근
일단 첫 주유소에서 무조건 주유를 해야하므로 시작 비용을 첫 주유소의 가격으로 잡는다.
이제 다음에 어디 주유소를 갈지 봐야하는데 중간에 시작 주유소보다 싼곳이 있으면 거기까지 갈 수 있을 양의 기름만 넣으면 된다.
예를들어 시작 주유소가 5원, 바로 다음 주유소가 3거리에 2원 짜리가 있으면 5x3으로 15원만 내고 해당 주유소로 간다.
하지만 3거리에 8원짜리 주유소였다면 이 주유소는 건너 뛰고 다음 주유소까지 갈 양만 넣으면 된다.
따라서 일단 다음 주유소까지 갈 양만 시작 주유소에서 넣고, 다음 주유소가 더 싼지 확인한 후 싸다면 해당 주유소 가격으로 그 다음 주유소 까지 갈 많큼만 넣는 과정을 반복하고, 아니라면 첫 주유소 가격으로 그 다음 주유소까지 갈 양을 넣으면 모든 주유소를 확인하면 된다.
문제해결
> 주유소의 개수 N을 입력받고, 각 주유소 사이의 거리를 dist배열, 주유소의 가격을 fuel배열에 저장한다.
> 거리와 비용을 입력받고, 총 가격을 누적할 cost변수와, 현재 가장 싼 주유소의 비용을 prev에 잡아둔다.
> 0번 주유소부터 시작하므로 i=1부터 돌며 일단 i번째 주유소 까지의 기름 값을 계산해 누적한다.
> 현재i번 째 주유소의 가격이 prev보다 싼 값이면 해당 주유소로 바꿔준다(해당 주유소에서 주유할거다)
> 그럼 다음 주유소에선 갱신된 prev로 다음 주유소까지 계산되거나, 기존 prev로 계산되어 나간다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//13305번 주유소
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
long[] dist = new long[N];
long[] fuel = new long[N];
st = new StringTokenizer(br.readLine());
for(int i = 1; i < N; i++) dist[i] = Long.parseLong(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) fuel[i] = Long.parseLong(st.nextToken());
long cost = 0;
long prev = fuel[0];
for(int i = 1; i < N; i++) {
cost += prev * dist[i];
if(fuel[i] < prev) prev = fuel[i];
}
System.out.print(cost);
}
}
후기
연료채우기 문제에선 시작 기름이 주어지고 시작했는데 이 문제에선 무조건 첫 주유소에서 내가 얼마나 넣을지 정하고 가는 방향이었다. 따라서 매 주유소를 보며 더 싼 곳을 골라 갱신해주면 된다.
