주유소

문제

백준 13305번 - 주유소

언어

JavaScript

순서도

가장 왼쪽 도시부터 하나의 도시만큼씩 이동해가며,
기름 가격을 비교합니다.
1. 만약 현재 기록해놓은 기름 가격보다 작다면, 기름 가격을 갱신합니다.
2. 기록해놓은 기름 가격보다 크다면, 갱신하지 않습니다.
다음 도시의 거리만큼 기름을 넣습니다.
가장 오른쪽 도시에 도착할 때까지 위 과정을 반복합니다.

문제 풀이 step 1

문제에 대한 설명은 다음과 같습니다.
어떤 나라에 N 개의 도시가 있고, 이 도시들은 일직선 도로 위에 있습니다.
제일 왼쪽 도시에서 오른쪽 도시로 자동차를 이용해서 이동할 예정입니다.
인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있습니다.
처음 출발 시 자동차에 기름이 없어 주유소에서 기름을 넣고 출발해야 합니다.
기름통의 크기는 무제한이고 1 km 마다 1 리터의 기름을 소모합니다.
각 도시에는 단 하나의 주유소가 있고, 도시마다 주유소의 리터당 가격이 다를 수 있습니다.
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이가 주어집니다. 이 때, 제일 왼쪽 도시에서 오른쪽 도시로 이동하는 최소 비용을 계산하는 문제입니다.

문제 풀이 step 2

우선, 가장 왼쪽 도시에서의 기름값을 최소값으로 설정합니다.
다음 도시까지의 거리만큼 기름을 넣습니다.
그리고 도착한 도시에서의 기름값과 최소값을 비교해서 더 작은 값으로 최소값을 갱신합니다.
그리고 또 다음 도시까지의 거리만큼 기름을 넣습니다.
위 과정을 반복해가며, 가장 오른쪽 도시에 도착했을 때, 누적된 기름값을 출력하면 정답입니다.

문제 풀이 step 3

본 문제에서 각 도시 사이의 거리는 크게 의미가 없습니다. 각 도시의 기름값만 의미를 가집니다.
예를 들어, 기름값이 [5, 7, 9, 3, 5, 6, 1, 2] 과 같다고 가정하겠습니다.
- 이 때, 기름값을 최소로 넣으려면 어떻게 넣어야 할까요??
- 정답은 [5, 5, 5, 3, 3, 3, 1, 1] 입니다.
- 정답을 보시면, 내림차순으로 되어 있는 것을 확인하실 수 있으실 것입니다.
즉, 기름값이 작아질 때, 기름값을 갱신하고 기름을 넣으면 됩니다.
추가 설명은 주석으로 작성하겠습니다.

후기

처음에는 가장 오른쪽 도시부터 가장 왼쪽 도시까지 한 칸씩 이동하며, 기름의 최소값을 찾은 다음에 넣고, 범위를 갱신하고, 또 최소값을 찾고 넣고 하는 방식으로 풀었으나 시간초과가 발생했습니다.
융통성이 없어서, 맨 앞에서부터 최솟값을 기록한 채로 이동하는 방식을 바로 떠올리진 못했습니다.
- 이미 도시를 지나갔지만, 최소값을 기록해놓으면, 지나간 도시의 기름을 넣을 수 있다는 것!!
- 그리디는 이런 방식의 문제가 많은 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	// 범위가 너무 크기 때문에 BigInt 를 사용해야 합니다.
	const streets = input[1].split(" ").map(BigInt);
	const prices = input[2].split(" ").map(BigInt);

	let ans = 0n;
	// 기름의 최솟값의 index 를 시작 도시의 기름값으로 초기화
	let minIndex = 0;
	for (let i = 0; i < n - 1; i++) {
		// 도착한 도시의 기름값이 더 작다면, 기름의 최솟값의 index 를 갱신
		if (prices[i] < prices[minIndex]) minIndex = i;

		// 다음 도시까지의 거리만큼 기름 넣기
		ans += streets[i] * prices[minIndex];
	}

	return String(ans);
};

console.log(solution(input));