취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2819번 문제인 상근이의 로봇이다.
문제는 아래 링크를 확인하자.

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

원점과 각 조사점 사이의 거리들을 모두 합한 dist라는 숫자를 만들고, 각 움직임에 따라 멀어진 점의 수, 가까워진 수를 이분 탐색(binary search)를 통해 세면서 dist를 갱신하는 식으로 문제를 해결할 수 있다.

찾고자하는 index가를 확실히 하고 그에 맞게 dist를 조정하는 식을 세워주자.

글쓴이는 전체 범위를 벗어나는 -1000001과 1000001을 배열에 같이 넣는 방식으로 찾고자하는 index가 항상 존재하게끔 조절하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;

int X[100002];
int Y[100002];

ll dist = 0;

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

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		X[i] = x, Y[i] = y;
		dist += abs(x) + abs(y);
	}
	X[N] = -1000001, X[N + 1] = 1000001;
	Y[N] = -1000001, Y[N + 1] = 1000001;
	N += 2;
	sort(X, X + N);
	sort(Y, Y + N);

	int x = 0, y = 0;
	string s; cin >> s;
	for (auto c : s) {
		if (c == 'I') { // east
			int L = 0, R = N - 1;
			while (L < R) { // L을 x보다 큰 수를 가리키는 최소 인덱스로
				int mid = (L + R) / 2;
				if (X[mid] <= x) L = mid + 1;
				else R = mid;
			}
			dist += 2 * L - N;
			cout << dist << '\n';
			x++;
		}
		else if (c == 'Z') { // west
			int L = 0, R = N - 1;
			while (L < R) { // R을 x보다 작은 수를 가리키는 최대 인덱스로
				int mid = (L + R) / 2 + 1;
				if (x <= X[mid])  R = mid - 1;
				else L = mid;
			}
			dist += (N - 2) - 2 * R;
			cout << dist << '\n';
			x--;
		}
		else if (c == 'S') { // north
			int L = 0, R = N - 1;
			while (L < R) { // L을 y보다 큰 수를 가리키는 최소 인덱스로
				int mid = (L + R) / 2;
				if (Y[mid] <= y) L = mid + 1;
				else R = mid;
			}
			dist += 2 * L - N;
			cout << dist << '\n';
			y++;
		}
		else { // south
			int L = 0, R = N - 1;
			while (L < R) { // R을 y보다 작은 수를 가리키는 최대 인덱스로
				int mid = (L + R) / 2 + 1;
				if (y <= Y[mid])  R = mid - 1;
				else L = mid;
			}
			dist += (N - 2) - 2 * R;
			cout << dist << '\n';
			y--;
		}
	}
}