200122 BOJ 2819 상근이의 로봇

수학 + ...

- 지문대로 해보면 식을 세울 수 있다. (x, y : 현재 위치    xi, yi : 조사점들    n : 조사점의 갯수)

- 이 식을 빠르게 구하려면 정렬 + 이분 탐색, 부분 합 필요

- 푸는 방법이 꼭 이것만 있는 것은 아니다 ㅎㅎ;

풀이 순서

1. 입력 받은 조사점들을 크기 순으로 정렬한다.

2. 부분 합을 구해 놓는다.

3. 현재 위치 보다 큰 x, y 좌표를 찾는다. 그 좌표가 위 식에서 부호가 바뀌는 곳 이다.

4. 식 대로 계산한다.

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define sws ios::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
int N, M, x, y;
 
int X[100002];
int Y[100002];
ll sum_X[100002];
ll sum_Y[100002];
int main() {
    sws;
    string cmd;
 
    cin >> N >> M;
    FOR(i, 0, N) {
        cin >> x >> y;
        X[i] = x;
        Y[i] = y;
    }
    cin >> cmd;
 
    sort(X, X + N);
    sort(Y, Y + N);
 
    sum_X[0] = X[0];
    sum_Y[0] = Y[0];
 
    FOR(i, 1, N) {
        sum_X[i] = sum_X[i - 1] + X[i];
        sum_Y[i] = sum_Y[i - 1] + Y[i];
    }
 
    int now_x = 0, now_y = 0;
 
    for (char c : cmd) { // 이동
        switch (c)
        {
        case 'S':
            now_y++;
            break;
        case 'J':
            now_y--;
            break;
        case 'I':
            now_x++;
            break;
        case 'Z':
            now_x--;
            break;
        default:
            break;
        }
 
        int i = upper_bound(X, X + N, now_x) - X;
        int j = upper_bound(Y, Y + N, now_y) - Y;
        ll left, right;
 
        if (i == 0) left = (-1) * now_x * N + sum_X[N - 1];
        else left = -sum_X[i - 1] * 2 - now_x * (N - 2 * i) + sum_X[N - 1];
 
        if (j == 0) right = (-1) * now_y * N + sum_Y[N - 1];
        else right = -sum_Y[j - 1] * 2 - now_y * (N -  2 * j) + sum_Y[N - 1];
 
        cout << left + right << endl;
    }
}