[C++] 백준 25395번: 커넥티드 카 실험

문제 링크

25395번: 커넥티드 카 실험

문제 요약

커넥티드 카들이 일직선 상에 놓여 있다. 커넥티드 카가 이동해서 다른 커넥티드 카가 있는 곳에 도착하면, 둘은 연결되게 된다. 커넥티드 카는 거리 1을 이동하는 데에 연료 1을 소비한다.
커넥티드 카들의 위치, 연료, 시작하는 카의 번호가 주어질 때, 연결될 수 있는 커넥티드 카의 번호를 모두 출력해야 한다.

접근 방법

S에서 시작해서 양쪽으로 뻗어나가면서 최댓값과 최솟값을 갱신해주면 되는 문제입니다.

1. S의 위치와 연료를 통해서 방문할 수 있는 범위를 먼저 계산합니다.
2. 범위 내에 있는, 방문할 수 있는 점들을 모두 방문합니다.
3. 방문하면서 방문 가능한 범위의 최댓값과 최솟값을 계산해서 임시로 저장해둡니다.
4. 방문이 완료되면 계산해둔 최댓값과 최솟값을 이용해서 범위를 다시 갱신해주고 2 ~ 3을 반복해주면 됩니다.

5 3
10 20 30 40 50
1 1 10 100 1

위처럼 오른쪽을 방문했다가 왼쪽으로 다시 가는 경우 방문 가능한 점이 더 많아질 수 있기 때문에, 왼쪽/오른쪽 모두 방문하면서 최댓값과 최솟값을 구해준 뒤에 범위를 갱신해 주었습니다.

코드

#include <bits/stdc++.h>

using namespace std;
using std::cout;

const int MAX = 1000001;
int x[MAX], h[MAX];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, s;
	cin >> n >> s;

	for (int i = 1; i <= n; i++)
		cin >> x[i];

	for (int i = 1; i <= n; i++)
		cin >> h[i];

	int low = s, high = s;
	int l = x[low] - h[s], r = x[high] + h[s];
	int min_ = 1e9, max_ = 0;
	while (1) {
		for (int i = low - 1; i >= 1; i--) {
			if (x[i] >= l) {
				min_ = min(min_, x[i] - h[i]);
				max_ = max(max_, x[i] + h[i]);
				low = i;
			}
			else {
				break;
			}
		}

		for (int i = high + 1; i <= n; i++) {
			if (x[i] <= r) {
				min_ = min(min_, x[i] - h[i]);
				max_ = max(max_, x[i] + h[i]);
				high = i;
			}
			else {
				break;
			}
		}

		if (l == min_ && r == max_)
			break;

		l = min_;
		r = max_;
	}

	for (int i = low; i <= high; i++)
		cout << i << ' ';
	cout << '\n';
	return 0;
}