이 문제는 주어진 5000개의 정수 중 3개의 정수를 합해 만들 수 있는 0에 가장 가까운 정수를 만들 수 있는 세 정수를 출력하는 문제이다.
들어온 N개의 정수를 정렬하고, 가장 작은 정수서부터 그 정수를 포함하는 0에 가장 가까운 합을 투포인터를 이용하여 계산해내면 O(N^2)의 시간 내로 문제를 해결할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
ll liq[5000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
cin >> liq[i];
}
sort(liq, liq + N);
ll ans = 999999999999999LL;
ll a, b, c;
for (int i = 0; i < N; i++) {
ll liqi = liq[i];
int L = i + 1, R = N - 1;
while (L < R) {
ll current = liq[L] + liq[R] + liqi;
if (abs(current) < ans) {
ans = abs(current);
a = liqi, b = liq[L], c = liq[R];
}
if (current < 0) L++;
else R--;
}
}
cout << a << ' ' << b << ' ' << c;
}
이 문제에서는, 3차원 좌표에 주어진 N개의 행성들을 모두 이을 수 있는 터널을 만드는 것이 목표이다.
이 문제는 각 N개의 행성들을 그래프의 노드라고 생각하고, 서로 다른 두 행성 사이에 두 행성 사이 거리를 가중치로 갖는 간선이 있는 완전그래프에서 MST(최소신장트리)를 찾는 문제로 생각할 수 있다.
단, 노드의 개수가 최대 10만개까지 가능하므로, 모든 서로 다른 두 행성을 잇는 간선을 생각할 수는 없고(시간 면으로나 메모리 면으로나), MST에 쓰일 수 있는 간선의 후보를 잘 추려내야한다.
다음과 같은 관찰을 하자.
N개의 행성 중, 세 행성 p1, p2, p3가 대하여 x좌표가 오름차순으로 주어져있는 상황을 생각해보자.
이 상황에서, p1, p2 사이의 x좌표의 차가 p1, p2 사이의 거리이고 p2, p3 사이의 x좌표의 차가 p2, p3 사이의 거리이면 p1과 p3를 잇는 간선은 MST에 쓰일 수 없다. 그 증명은 다음과 같다:
p1과 p3을 잇는 간선이 spanning tree에 포함되어있다고 가정하자. 이 spanning tree에서 p1과 p3을 잇는 간선을 지운다면 MST는 두개의 connected component로 분리되게 된다. 이 때, p2는 p1이 포함되어 있는 component와 연결되어있거나 p3이 포함되어 있는 component와 연결되어있다. 각각의 경우 p2와 p3 / p2와 p1을 잇는 간선을 그으면 기존 spanning tree보다 더 적은 총합 가중치를 가진 spanning tree를 만들 수 있다.
위와 같은 증명과 같은 아이디어를 바탕으로, MST에 사용될 수 있는 후보 간선은 x좌표, y좌표, z좌표 순으로 정렬했을 때 서로 인접한 순서에 있는 노드를 잇는 에지들일 것임을 알 수 있다.
이 추려진 (최대 30만개의) 후보간선들을 이용하여 MST를 구하는 Kruskal(크루스칼) 알고리즘을 이용하면 문제를 해결할 수 있다.
아래 구현 코드에서, (예를 들어) x좌표를 기준으로 정렬된 인접한 두 노드를 잇는 간선을 후보간선으로 넣을 때 거리를 실제 거리 대신 두 노드의 x좌표의 차를 이용하고 있는데, 이렇게 구현해도 되는 이유는 실제 거리가 x좌표의 차가 아니면서 실제 MST 중 하나의 구성 에지라면 두 노드 사이의 거리를 구하게 되는 방향의 축으로 정렬할 때 인접하게 될 것이기 때문이다. (위의 "관찰의 증명"을 생각해보자.) 이 설명은 x를 y 또는 z로 바꿔도 마찬가지로 통한다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct P {
int x, y, z;
int idx;
};
struct E {
long long w;
int idx1, idx2;
};
bool cmpx(P p1, P p2) {
if (p1.x < p2.x) return 1;
else return 0;
}
bool cmpy(P p1, P p2) {
if (p1.y < p2.y) return 1;
else return 0;
}
bool cmpz(P p1, P p2) {
if (p1.z < p2.z) return 1;
else return 0;
}
bool cmpw(E e1, E e2) {
if (e1.w < e2.w) return 1;
else return 0;
}
int dset[100000];
int findf(int x) {
if (x == dset[x]) return x;
else return dset[x] = findf(dset[x]);
}
P arr[100000];
vector<E> edge;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
dset[i] = i;
}
for (int i = 0; i < N; i++) {
int x, y, z; cin >> x >> y >> z;
arr[i].x = x, arr[i].y = y, arr[i].z = z;
arr[i].idx = i;
}
sort(arr, arr + N, cmpx);
for (int i = 1; i < N; i++) {
E e;
e.w = arr[i].x - arr[i - 1].x;
e.idx1 = arr[i].idx;
e.idx2 = arr[i - 1].idx;
edge.push_back(e);
}
sort(arr, arr + N, cmpy);
for (int i = 1; i < N; i++) {
E e;
e.w = arr[i].y - arr[i - 1].y;
e.idx1 = arr[i].idx;
e.idx2 = arr[i - 1].idx;
edge.push_back(e);
}
sort(arr, arr + N, cmpz);
for (int i = 1; i < N; i++) {
E e;
e.w = arr[i].z - arr[i - 1].z;
e.idx1 = arr[i].idx;
e.idx2 = arr[i - 1].idx;
edge.push_back(e);
}
sort(edge.begin(), edge.end(), cmpw);
long long ans = 0;
for (auto e : edge) {
int x = findf(e.idx1), y = findf(e.idx2);
if (x == y) continue;
dset[y] = x;
ans += e.w;
}
cout << ans;
}
1) 이 "다이아몬드 모양"은 가장 위쪽(r값이 작은 쪽)에 하나의 꼭짓점 1이 존재한다.
2) 그 꼭짓점에서 왼쪽 아래방향, 오른쪽 아래방향으로 T-1개의 1이 연속적으로 있어야 한다. 각 방향의 T-1번째 1의 위치를 각각 X, Y라 하자.
3) X에서 오른쪽 아래방향, Y에서 왼쪽 아래방향으로 T-1개의 1이 연속적으로 있어야 한다.
위와 같이 생각을 바탕으로, 주어진 2차원 배열에서 각 꼭짓점에서 "왼쪽 아래방향으로 연속한 1의 개수"와 "오른쪽 아래방향으로 연속한 1의 개수"를 미리 계산해둔다면 "가장 위쪽 꼭짓점"으로 하는 다이아몬드의 존재를 빠르게 계산할 수 있게 된다.
모든 "다이아몬드 모양"은 "가장 위쪽 꼭짓점"이 존재하므로, 위의 탐색만을 하여도 충분하다.
탐색 과정에서, 이미 찾은 크기보다 작거나 같은 다이아몬드는 발견하더라도 답에 영향을 주지 않으므로 찾은 크기보다 큰 다이아몬드만을 탐색해나가면 빠르게 문제를 해결할 수 있다.
구현시 배열의 범위를 벗어나지 않게 주의하자.
아래는 제출한 소스코드이다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string field[750];
int diag[750][750][2]; // [i][j][x]: i행 j열 / x = 0: down left, x = 1: down right방향
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int R, C; cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> field[i];
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (field[r][c] == '0') continue;
if (diag[r][c][0] == 0) { // down_left방향 탐색
int rr = r, cc = c;
int level = 0;
while (rr < R && cc >= 0) {
if (field[rr][cc] == '0') break;
level++;
rr++; cc--;
}
for (int i = 0; i < level; i++) {
diag[r + i][c - i][0] = level - i;
}
}
if (diag[r][c][1] == 0) { // down_right방향 탐색
int rr = r, cc = c;
int level = 0;
while (rr < R && cc < C) {
if (field[rr][cc] == '0') break;
level++;
rr++; cc++;
}
for (int i = 0; i < level; i++) {
diag[r + i][c + i][1] = level - i;
}
}
}
}
int ans = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (field[r][c] == '0') continue;
int T = min(diag[r][c][0], diag[r][c][1]);
while (T > ans) {
if (diag[r + T - 1][c - T + 1][1] >= T && diag[r + T - 1][c + T - 1][0] >= T)
ans = T;
T--;
}
}
}
cout << ans;
}
"조커 박스"는 다른 박스와 상관없이 모든 스티커를 담을 수 있으므로, 여러 스티커가 혼합되어있는 상자는 그냥 조커박스로 쓰일 상자에 뭉쳐버리는 게 한가지 좋은 방법이 될 수 있다.
그러나, 단일 스티커 상자의 경우 "조커 박스"에 합치지 않아도 이미 정리가 된 상자로 볼 수 있기 때문에 단일 스티커 상자는 안에 들어있는 스티커별로 각각 1개씩은 "조커 박스"로 합치지 않아도 된다.
상자가 빈 상자라면 아무 계산도 하지 않고 넘기자.
이 관찰을 그대로 구현하면 문제를 해결할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
bool visited[51];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int ans = 0;
int N, M; cin >> N >> M;
while (N--) {
int type = 0;
bool multitype = 0;
for (int i = 1; i <= M; i++) {
int x; cin >> x;
if (x > 0) {
if (type == 0) type = i;
else multitype = 1;
}
}
if (type == 0) continue;
else if (multitype || visited[type]) ans++;
else visited[type] = 1;
}
if (ans > 0) ans--;
cout << ans;
}