BOJ 3126 : 반역의 원철이

• 문제 링크 : boj.kr/3126
• 난이도 : G4
• 태그 : 브루트포스, 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
ll dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
struct d {
    ll dir[8];
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cout.precision(6); cout << fixed;

    ll xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<d> arr(n+1);
    int curr = 0;
    for(int i = 1; i <= n; i++) {
        curr += s[i-1] - '0';
        curr %= 8;
        arr[i] = arr[i-1];
        arr[i].dir[curr] += 1;
    }

    ll ans = LLONG_MAX;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 8; j++) {
            d result = arr[i];
            for(int k = 0; k < 8; k++) {
                int idx = (k+j)%8;
                result.dir[k] += arr[n].dir[idx] - arr[i].dir[idx];
            }
            ll resX, resY;
            resX = xa;
            resY = ya;
            for(int j = 0; j < 8; j++) {
                resX += dx[j] * result.dir[j];
                resY += dy[j] * result.dir[j];
            }
            ans = min(ans, (xb-resX)*(xb-resX) + (yb-resY)*(yb-resY));
        }
    }
    cout << sqrtl(ans);

    return 0;
}

---

풀이

어느 시점까지의 각각의 방향으로 이동한 횟수를 누적합을 이용해 저장한다.

모든 시점의 이동 횟수를 구했으므로 특정 시점에서 다르게 이동한 경우 도달할 위치를 O(1)로 구할 수 있다.

모든 경우에 대해서 다르게 이동한 경우를 따져보면 답을 구할 수 있다.