A번째 용액, B번째 용액을 골라서 확인을 하되, A번째 용액에 대해서는 for문 을 돌고, 각각 A번째용액에 대하여, B번째 용액을 결정할 때, 바이너리 서치 개념을 적용해서 풀어보았습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int a[100005];
int n;
int f, s, val;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
}
f = a[0];
s = a[1];
val = abs(f+s);
for (int i = 0; i < n - 1; i++) {
int first = a[i];
int left = i + 1; // [left, right]
int right = n - 1;
while (left < right) {
int mid = (left + right) / 2;
int& second = a[mid];
int sum = first + second;
if (sum < 0) {
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
left = mid + 1;
}
else if (sum > 0) {
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
right = mid;
}
else {
cout << first << ' ' << a[mid] << endl;
return 0;
}
}
int second = a[right];
int sum = first + second;
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
second = a[left];
sum = first + second;
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
}
cout << f << ' ' << s << endl;
return 0;
}
이 풀이 외에도 O(N)으로도 풀이가 가능하다는 것을 알게 되었습니다.
배열이 정렬되어 있기 때문에, A번째에서 A+1번째로 이동할 때, 더 0에 가까운 값을 구하기 위해서는 B에서 B-1로 이동하는 경우는 있을 수 있으나 B+1에서 더 0에 가까운 값이 나올 수는 없기에 그리디하게 투포인터 형식으로 풀 수있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int arr[100005];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
int a, b, val;
a = arr[0], b = arr[n - 1];
val = abs(a + b);
int left = 0;
int right = n - 1;
while (left < right) {
int l, r, sum;
l = arr[left];
r = arr[right];
sum = l + r;
if (abs(sum) < val) {
val = abs(sum);
a = l;
b = r;
}
if (sum > 0) {
right--;
}
else {
left++;
}
}
printf("%d %d\n", a, b);
}
색깔별로 다른 vector에 저장한 뒤, 정렬하여 인접한 녀석 중 가까운 곳에 잇는 방식으로 풀 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> A[5005];
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int pos, col;
cin >> pos >> col;
A[col-1].push_back(pos);
}
for (int i = 0; i < N; i++) {
sort(A[i].begin(), A[i].end());
}
int ans = 0;
for (int j = 0; j < N; j++) {
for (int i = 0; i < A[j].size(); i++) {
int prev, next;
prev = next = 987654321;
if (i > 0) {
prev = A[j][i] - A[j][i - 1];
}
if (i + 1 < A[j].size()) {
next = A[j][i + 1] - A[j][i];
}
ans += min(prev, next);
}
}
cout << ans << endl;
return 0;
}
총N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다.N개의 방은 1번부터N번까지의 번호를 붙여 1번 방, 2번 방, …,N번 방으로 부른다. 통로는 정확히N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.
이 조건을 보아서, 이 Graph는 트리입니다.
서로 다른곳에 있는 로봇이 만나기 위해 이동해야 하는 거리의 최소값을 구해야 합니다. 두 점의 최단거리 문제이죠.
그리고 한 Edge에 대해서는 이동하지 않고 통신을 할 수 있기 때문에, 그냥 최단거리 문제는 아닙니다.
Edge의 Weight값이 균일하지 않기 때문에 Dijkstra Shortest Path 알고리즘으로 풀 수 있으며, 한 Edge의 값은 제거할 수 있기 때문에 지난 Edge 중 가장 큰 Edge weight 값을 가지고 있다가, 총 거리에서 해당 Largest Edge weight를 제거하면 정답이 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 100005
vector<pii> edges[MAXN];
bool visit[MAXN];
struct State {
int pos, totallen, maxseg;
bool operator<(const State& rhs) const {
return totallen > rhs.totallen;
}
};
int main() {
int N, A, B;
cin >> N >> A >> B;
for (int i = 1; i < N; i++) {
int src, dst, len;
cin >> src >> dst >> len;
edges[src].push_back(make_pair(dst, len));
edges[dst].push_back(make_pair(src, len));
}
priority_queue<State> pq;
pq.push({ A, 0, 0 });
while (pq.size()) {
State state = pq.top(); pq.pop();
int pos = state.pos;
visit[pos] = true;
if (pos == B) {
cout << (state.totallen - state.maxseg) << endl;
return 0;
}
for (auto next : edges[pos]) {
int next_pos = next.first;
int next_seglen = next.second;
if (visit[next_pos] == false) {
pq.push({ next.first, state.totallen + next_seglen, max(state.maxseg, next_seglen) });
}
}
}
}
아이디어를 생각해내기 좀 어려웠는데요, 풀고 나서도 왜 이게 풀렸는지 지금 100% 이해가 된 상태는 아닙니다.
일단 Graph 문제로 환원하여 생각을 하였고, 외부와 직/간접적으로 연결된 녀석들은 물이 셀 수 있습니다.
직접적으로 연결된 녀석은 그 연결된 구멍의 높이만큼 물이 세어나가게 되고, 간접적으로 연결된 녀석은 조건에 따라서 물이 세어나갈수도 있고 아닐 수도 있습니다.
외부에서 부터 Graph 탐색을 한다고 하였을 때, 간접적으로 외부와 연결된 내부 공간들이 탐색이 되게 되는데,
이때 외부로 연결되는 구멍의 높이가 높아지는 경우와 낮아지는 경우가 있습니다.
외부와 연결되는 구멍의 높이가 높아지는 경우는 최근 구멍의 높이만큼 물이 줄줄 세개 됩니다.
구멍의 높이가 낮아지는 경우는, 최근 연결된 녀석의 수심만큼만 물이 줄줄 세어나가게 됩니다.
이러한 특징을 활용해서 변형된 Dijkstra 최단거리 알고리즘으로 문제를 풀이했습니다.
구멍 높이가 낮은 녀석부터 먼저 탐색하도록 하였고, 이게 문제가 풀릴지 아닐지 몰랐는데, 풀리긴 하더군요.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
struct Edge{
int x, y, h;
};
struct State {
int x, y, sx, sy, h;
bool operator<(const struct State& rhs) const {
return h > rhs.h;
}
};
vector<Edge> edges[1005][1005];
int height[1005][1005];
bool visit[1005][1005];
int main() {
int N, M, H;
scanf("%d%d%d", &N, &M, &H);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
height[i][j] = H;
}
}
for (int i = 0; i <= N; i++) {
for (int j = 1; j <= M; j++) {
/*
(i,j) ~ (i+1, j)
*/
int v;
scanf("%d", &v);
if (~v) {
edges[i][j].push_back({ i + 1, j, v });
edges[i + 1][j].push_back({ i, j, v });
}
}
}
for (int j = 1; j <= N; j++) {
for (int i = 0; i <= M; i++) {
/*
(j, i) ~ (j, i+1)
*/
int v;
scanf("%d", &v);
if (~v) {
edges[j][i].push_back({ j, i + 1, v });
edges[j][i + 1].push_back({ j, i, v });
}
}
}
priority_queue<State> pq;
for (int i = 0; i <= M + 1; i++) {
int x = 0;
int y = i;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 0; i <= M + 1; i++) {
int x = N + 1;
int y = i;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 1; i <= N; i++) {
int x = i;
int y = 0;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 1; i <= N; i++) {
int x = i;
int y = M + 1;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
while (pq.size()) {
auto state = pq.top(); pq.pop();
int x = state.x;
int y = state.y;
int sx = state.sx;
int sy = state.sy;
int h = state.h;
if (visit[x][y] == false) {
visit[x][y] = true;
height[x][y] = min(height[x][y], max(h, height[sx][sy]));
for (auto eg : edges[x][y]) {
if (visit[eg.x][eg.y] == false) {
pq.push({ eg.x, eg.y, x, y, eg.h });
}
}
}
}
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
ans += height[i][j];
}
}
printf("%d\n", ans);
return 0;
}
