백준 - 주유소 (13305) [C++]

 이 문제는 그리디를 이용해서 푸는 문제이다. 내가 생각한 방법은 현재 위치의 cost와 다음 위치들의 cost들을 비교하고, 만약 현재 cost보다 크거나 같으면 넘어가고, 작은 cost가 나올때까지 간다음, 현재 위치에서 그만큼의 연료를 충전하고 해당 위치로 이동하는 것이었다. 그러나 구현 실수로 정답이 나오지 않았는데, 이는 for문을 돌리다가 현재 cost보다 작은 cost가 나오면 바로 break를 해버려 해당 위치까지 이동하는 계산이 빠졌기 때문이다. 다시 구현하니 바로 정답이 나왔다.

 

 한 가지 주의할 점은 만약 while (true) 로 하고 if (index == N - 1) break; 이런식으로 구현하면 무한 루프에 돌아가게 되는데, 이는 만약 for문이 break로 끝나지 않고 끝까지 갔을 경우 next가 N과 같은 값을 갖게 된다. 이는 next++이 적용된 후 next < N을 검사하고 false이면 for문이 종료되기 때문이다. 따라서 ==이 아닌 >= 을 사용해야 한다.

 

 

 

#include <iostream>

using namespace std;

#define CITYMAX 100000

long long roadLength[CITYMAX];
long long cost[CITYMAX];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int length;

		cin >> length;
		roadLength[i] = length;
	}

	roadLength[N - 1] = 0;
	for (int i = 0; i < N; i++) {
		int c;

		cin >> c;

		if (i == N - 1) {
			cost[i] = 1000000001;
			continue;
		}
		cost[i] = c;
	}

	int index = 0;

	long long answer = 0;

	if (N == 2) {
		answer += roadLength[0] * cost[0];

		cout << answer << '\n';

		return 0;
	}

	while (index <= N - 1) {
		long long presentCost = cost[index];

		long long cnt = 0;
		int next;
		for (next = index + 1; next < N; next++) {
			if (presentCost > cost[next]) {
				cnt += roadLength[next - 1] * presentCost; // 여기 빼먹으면 안됨
				break;
			}
			else {
				cnt += roadLength[next - 1] * presentCost;
			}
		}
		if (cnt == 0) {
			answer += presentCost * roadLength[index];
			index++;
		}
		else {
			answer += cnt;
			index = next;
		}
	}

	cout << answer << '\n';

	return 0;
}