[JAVA] BOJ(백준) - 주유소 - 13305번

문제내용

https://www.acmicpc.net/problem/13305

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원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

 

---

문제 접근 방법

도시 끝에서 끝까지 갈때까지 드는 최소비용의 주유값을 구하는 문제이다.

문제에서 1키로당 1리터의 기름이 사용된다 했기 때문에 당연히 1리터 기름값이 최대한 싼곳에서 최대한 주유를 많이 해놔야 최솟값이 나온다 생각했다.

 

그러기 위해선 제일 왼쪽도시부터 시작하여 마지막 도시(n) 바로전 도시까지(n-1) 주유값을 살펴보면서 주유값이 현재있는 도시보다 싼값이라면 그 도시까지 이동해서 기름을 채우면된다.

위의 것을 만족하기전 고려해야할 조건은

첫번째 : 1번 도시에서 출발할때는 무조건 첫번째 도시에서 다음도시까지는 기름을 채워야한다는것.

두번째 : n번 도시는 어차피 도착지이기 때문에 굳이 기름값을 고려할 필요가 없다는것.

두가지 조건을 만족하면서 도시 하나 하나씩 순회하며 기름값이 싼곳에서 주유를 받으면되는 것이다. 그리고 주유할 때 다시 뒤의 도시들과 기름값을 비교하는 식으로 하면된다.

 

예를 들어 입력값이

7

4 2 5 3 3 3
5 3 2 7 4 1 0

이라고 하면 아래와 같이 표를 만들어 생각할 수 있다.

idx	0	1	2	3	4	5	6
road(dis)	0	4	2	5	3	3	3
oil(city)	5	3	2	7	4	1	0

표를 보면서 계산해보면 다음순서로 최솟값을 구할 수있다.

1. idx 0번 도시에서 다음 도시들중 하나로 이동하기 위해선 무조건 주유를 해야한다.

2. 현재도시(0번도시)를 1번~5번도시까지 기름값을 비교하면서 싼곳까지는 가도록 한다.

이말은 1번도시가 0번도시(현재도시)보다 기름값이 싸기때문에 일단 이동은 1번도시까지 하면된다는 말이고 1번도시 까지는 20의 비용이든다 (현재 최솟값: 20)

3. 1번도시 도착 후 1번도시 기름값과 2~5번 도시까지 기름값을 비교하면서 더싼 기름값이 나오는 도시를 찾는다. 그렇게 되면 2번 도시의 기름값이 더 싸기때문에 1번도시에서는 2번도시까지만 이동하면된다. 이때 드는 비용은 6이다. (현재 최솟값: 20+6)

4. 2번 도시 도착후 2번도시 기름값과 3~5번 도시까지 기름값을 비교하면서 다싼 기름값이 나오는 도시를 찾는다. 이때는 현재도시(2번도시)에 비해 3,4번 도시는 더 비싸고 5번 도시는 더 싸다는걸 알수 있다. 따라서 2번도시에서 5번도시까지 이동할만큼의 기름을 채우면된다. 이때 드는비용은 2*(5+3+3)=22 이다.(현재 최솟값: 20+6+22)

5. 5번도시에선 마지막도시까지 가기 위해선 그냥 무조건 5번도시의 기름값으로 3리터만큼 채워서 6번도시로 가면된다.

 

위의 과정을 통해 최소비용은 (0번~1번) + (1번~2번) + (2번~5번) + (5번~6번) 이라고 볼 수 있다.

즉, 20 + 6 + 22 + 3 = 51 이라는 최솟값 비용이 나오게된다.

 

기억해야 할껀 기름값이 최대한 싼곳에서 그다음 도시중 기름값이 싼 도시까지의 이동거리를 고려하여 주유하면 된다는 점이다.

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static long[] road;//거리
	static long[] oil;//기름값
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		road = new long[n];//0번인덱스는 안씀
		oil = new long[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<road.length; i++) {
			road[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<oil.length; i++) {
			oil[i] = Integer.parseInt(st.nextToken());
		}
		
		long crrOil= oil[0];//현재 기름값
		long crrRoad = road[1];//현재 가야하는 이동거리
		long min = 0;//최솟값
		for(int i=1; i<oil.length-1; i++) {
			if(oil[i]<crrOil) {//현재 기름값이 다음 도시의 기름값보다 클때
				min += crrOil*crrRoad;//최솟값(다음도시로 이동)
				crrOil = oil[i];//도시 이동 후 그도시의 기름값으로 갱신
				crrRoad = road[i+1];//도시 이동 후 다음 도시의 까지의 거리로 갱신
			}else {//현재 기름값이 더 작을때
				//이땐 현재 이동해야하는 거리를 더해준다. 
				crrRoad += road[i+1]; 
			}
		}
		min += crrOil*crrRoad;//마지막도시로 이동값 계산
		System.out.println(min);
	}
}

 

---

마치며

참고로 자바는 int형끼리 계산일때 오버플로가 나는 수가 나오면 그 수를 받아주는 변수 타입이 long형이더라도 안된다고한다. 무조건 입력값 출력값 모두 long형으로 해주도록하자.