[BOJ 24618] Robot Instructions

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

24618번: Robot Instructions

 

- 문제 요약

 

Bessie는 최근 선물 받은 로봇을 제어하는 법을 배우고 있습니다.

처음 로봇은 (0,0) 위치에 있고, Bessie는 이 로봇이 (xi, yi)까지 가기를 원합니다.

Bessie는 로봇에게 N(1<=N<=40)가지의 명령을 수행하게 하려 합니다.

로봇은 상하좌우 네 방향으로 xi 또는 yi만큼 움직입니다.

 

 

- 알고리즘 정리

 

Meet in the middle 알고리즘을 활용해서 풀면 됩니다.

만약 로봇이 (xi,yi)에 있는 경우에는 시간복잡도 낭비 없이 바로 결괏값이 나오도록 했습니다.

 

 

- 코드 작성

 

#include <bits/stdc++.h>

using namespace std;

using P = pair<long long, long long>;
P operator+(P a, P b) { return {a.first + b.first, a.second + b.second}; }
P operator-(P a, P b) { return {a.first - b.first, a.second - b.second}; }

vector<pair<P, int>> all_subsets(const vector<P> &dirs) {
	vector<pair<P, int>> v{{}};
	for (const P &d : dirs) {
		v.resize(2 * v.size());
		for (int i = 0; i < v.size() / 2; i++) {
			v[i + v.size() / 2] = {v[i].first + d, v[i].second + 1};
		}
	}
	sort(v.begin(), v.end());
	return v;
}

int main() {
	int N;
	cin >> N;
	P goal;
	cin >> goal.first >> goal.second;
	vector<P> dirs(N);
	for (auto &d : dirs) {
		cin >> d.first >> d.second;
	}
	vector<pair<P, int>> a = all_subsets(vector<P>(begin(dirs), begin(dirs) + N / 2));
	vector<pair<P, int>> b = all_subsets(vector<P>(begin(dirs) + N / 2, end(dirs)));
	reverse(b.begin(), b.end());
	vector<long long> ans(N + 1);
	vector<int> with_num;
	P rest_prev{1e18, 1e18};
	int ib = 0;
	for (const auto &[offset, num] : a) {
		const P rest = goal - offset;
		if (rest != rest_prev) {
			rest_prev = rest;
			with_num = vector<int>(N - N / 2 + 1);
			for (; ib < b.size() && b.at(ib).first > rest; ++ib);
			for (; ib < b.size() && b.at(ib).first == rest; ++ib) {
				++with_num.at(b.at(ib).second);
			}
		}
		for (int i = 0; i < with_num.size(); i++) {
			ans[i + num] += with_num[i];
		}
	}
	for (int i = 1; i <= N; i++) {
		cout << ans[i] << "\n";
	}
}

코드 제출 결과