https://www.acmicpc.net/problem/13305
문제 요약
N개의 도시가 일직선으로 주어진다. 제일 왼쪽 도시에서 제일 오른쪽 도시로 차를 타고 이동하려고 한다.
인접한 두 도시 간의 간격은 서로 다를 수 있으며, km 단위로 주어진다.
처음에는 차에 기름이 없어 주유소에서 기름을 넣고 출발해야 한다. 기름통의 크기는 무제한이다.
1km을 이동할 때마다 1리터의 기름을 사용한다.
각 도시에는 단 하나의 주유소가 있으며, 각 도시마다 기름의 가격은 서로 다를 수 있다. 가격은 원 단위이다.
각 도시 주유소의 기름 가격, 도시를 연결하는 도로의 길이를 받아 이동하는 최소 비용을 구하여라.
도시 개수 N은 최대 10만이다.
제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10억이다.
기름의 리터 당 가격은 최대 10억이다.
문제 접근
주어진 문제 상황을 고려하면 기름이 가장 저렴한 도시에서 필요한 기름을 모두 사는 것이 효율적임을 알 수 있다.
다만 기름이 가장 저렴한 도시에 도달하는 과정에서 필요한 기름은 어디서 살 지가 중요하다.
당연히 가장 저렴한 도시에 도달하기 전의 가장 저렴한 도시에서 기름을 사면 될 것 같다.
이를 재귀적으로 반복해서 생각하면, 현재 위치 이전의 가장 저렴한 도시에서 현재까지 도달하는 데 필요한 기름을 모두 사도록 하는 것이 문제를 해결하는 방법임을 알 수 있다.
풀이
기본적인 아이디어는 다음과 같다.
- 도시를 순서대로 훑어 현재 도시 이전에 가장 저렴한 기름 가격을 기록한다.
- 현재 도시까지 구매할 수 있는 가장 저렴한 기름 가격과 도시 간의 이동 거리를 곱하고, 이를 덧셈으로 누적하여 답을 얻는다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 받기
int N = Integer.parseInt(br.readLine());
int[] dist = new int[N-1];
StringTokenizer stDist = new StringTokenizer(br.readLine());
for (int i = 0; i < N-1; i++) {
dist[i] = Integer.parseInt(stDist.nextToken());
}
int[] oilCost = new int[N];
StringTokenizer stCost = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
oilCost[i] = Integer.parseInt(stCost.nextToken());
}
// 현재까지의 최소 가격을 기록하는 배열
int[] minCost = new int[N-1]; // 마지막 마을은 필요 없으므로 N-1까지만 해도 됨
minCost[0] = oilCost[0]; // 첫번째 마을은 무조건 최소값
for (int i = 1; i < N-1; i++) {
minCost[i] = Math.min(minCost[i-1], oilCost[i]);
}
// 전체 비용을 계산하기
long answer = 0;
for (int i = 0; i < N-1; i++) {
answer += (long) minCost[i] * dist[i];
}
System.out.println(answer);
}
}회고
틀렸던 이유
주유소의 기름 가격과 주유소 간의 거리 각각은 모두 int 내에 나타낼 수 있지만, 두 수의 곱은 int를 넘어갈 수 있다는 점을 간과했다.
계산 값을 받는 변수가 long이어도 두 수가 각각 int로 선언되어 있으면 그 결과도 int로 얻어져서 값이 누락된 것 같다.
이렇듯 큰 값이 가능한 경우에는 int 범위를 넘어가지 않는지 미리 생각하는게 중요하다...!
