11월 알고리즘 공부 : 최소 외접원/구, 가장 가까운 두 점, 번사이드 보조정리 등
최근 글 작성 빈도가 현저히 낮아졌는데, 바쁘다거나 그런 이유보다는 2022년 막바지로 갈수록 의욕이 떨어져간다는 표현이 맞는 것 같다.
그래도 아직 백준에서 2022년 푼 문제 수 랭킹 1위를 유지하고 있기 때문에 최소한 유종의 미라도 거두기 위해 연말까지는 열심히 풀어보려고 한다.
아무튼 11월 중순동안 공부한 내용들을 나중에 스스로 참고할 수 있도록 정리해보려고 한다.
백준 BOJ 2626번 : 헬기착륙장
문제 난이도 : Diamond V
알고리즘 분류 : 최소 외접원
2차원 좌표 평면 상의 N개의 점이 주어질 때 이들을 모두 포함하는 가장 작은 원의 중심과 반지름을 구하는 문제이다.
세 점을 지나는 원이 반드시 존재함을 이용하여 풀이하는 문제이다. (여담으로, 타원의 경우 최대 다섯 개의 점을 지나는 타원이 반드시 존재한다. 어떤 점을 잡아도 무조건 지나는 원이 있으려면 3개의 점이 최대이고, 구의 경우에는 4개이다.)
아래와 같이 3중 for문을 이용하여 가장 바깥쪽의 세 점을 지나는 원을 구해주면 된다.
세 점을 지나는 원의 중심 좌표에 대한 식은 문제에서 알려준다.
3중 for문이므로 시간 복잡도가 O(N^3)처럼 보이지만, 실제로는 어떤 점이 현재 구한 원을 벗어나야만 for문 내부의 코드가 작동하므로 실질적인 작동 시간은 O(N)에 가깝다고 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct p { double x, y; };
double dis(p a, p b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(3);
int N; cin >> N;
vector<p> v(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;
p cen = {0, 0};
double r = 0;
for(int i=0; i<N; i++) {
if(dis(cen, v[i]) <= r) continue;
cen = v[i], r = 0;
for(int j=0; j<i; j++) {
if(dis(cen, v[j]) <= r) continue;
cen = {(v[i].x + v[j].x) / 2, (v[i].y + v[j].y) / 2};
r = dis(cen, v[i]);
for(int k=0; k<j; k++) {
if(dis(cen, v[k]) <= r) continue;
cen.x = ((pow(v[j].x, 2) - pow(v[k].x, 2) + pow(v[j].y, 2) - pow(v[k].y, 2)) * (v[i].y - v[j].y)
- (pow(v[j].x, 2) - pow(v[i].x, 2) + pow(v[j].y, 2) - pow(v[i].y, 2)) * (v[k].y - v[j].y))
/ ((v[i].x - v[j].x) * (v[k].y - v[j].y) * 2 - (v[k].x - v[j].x) * (v[i].y - v[j].y) * 2);
cen.y = ((pow(v[j].y, 2) - pow(v[k].y, 2) + pow(v[j].x, 2) - pow(v[k].x, 2)) * (v[i].x - v[j].x)
- (pow(v[j].y, 2) - pow(v[i].y, 2) + pow(v[j].x, 2) - pow(v[i].x, 2)) * (v[k].x - v[j].x))
/ ((v[i]. y- v[j].y) * (v[k].x - v[j].x) * 2 - (v[k].y - v[j].y) * (v[i].x - v[j].x) * 2);
r = dis(cen, v[i]);
}
}
}
if(abs(cen.x) < 1e-4) cen.x = 0;
if(abs(cen.y) < 1e-4) cen.y = 0;
cout << cen.x << " " << cen.y << "\n";
cout << r << "\n";
}
이 문제를 풀이하면 거의 비슷한 코드로 다음의 문제들을 풀 수 있다.
백준 BOJ 2389번 : 세상의 중심에서... (Platinum I)
백준 BOJ 13708번 : 모든 점을 포함하는 원 (Platinum I)
백준 BOJ 21182번 : Weird Flecks, But OK (Platinum I)
백준 BOJ 10517번 : Radar Coverage (Gold III)
풀이 코드는 거의 비슷하므로 생략한다.
백준 BOJ 11930번 : Smallest Enclosing Sphere
문제 난이도 : Diamond V
알고리즘 분류 : 최소 외접원, 3차원 기하학
3차원 좌표 상의 N개의 점이 주어질 때, 이 점들을 모두 포함하는 가장 작은 구의 반지름을 구하는 문제이다.
위 문제의 풀이를 확장시키면 풀이할 수 있지만, 식의 구현이 매우 복잡하다.
실제로 나와 같은 방식으로 휴리스틱 없이 풀이한 사람은 1명인 것으로 확인된다. (실행 시간이 0ms에 가까워야 함)
식으로 이 문제를 풀기 위해서는 다음의 2가지 식이 필요하다.
(1) 3차원 좌표 상에서 3개의 점을 지나는 원의 중심을 구하는 공식
(2) 3차원 좌표 상에서 4개의 점을 지나는 구의 중심을 구하는 공식
이들은 모두 행렬 식을 이용하여 풀이할 수 있는데, 역행렬을 구하는 과정이나 행렬 곱을 구하는 과정이 매우 복잡해서 자세한 설명은 아래의 코드로 대체한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct p { double x, y, z; };
double dis(p a, p b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(2);
int N; cin >> N;
vector<p> v(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y >> v[i].z;
p cen = {0, 0, 0};
double r = 0;
for(int i=0; i<N; i++) {
if(dis(cen, v[i]) <= r) continue;
cen = v[i], r = 0;
for(int j=0; j<i; j++) {
if(dis(cen, v[j]) <= r) continue;
cen = {(v[i].x + v[j].x) / 2, (v[i].y + v[j].y) / 2, (v[i].z + v[j].z) / 2};
r = dis(cen, v[i]);
for(int k=0; k<j; k++) {
if(dis(cen, v[k]) <= r) continue;
double ax = v[i].x, ay = v[i].y, az = v[i].z;
double bx = v[j].x, by = v[j].y, bz = v[j].z;
double cx = v[k].x, cy = v[k].y, cz = v[k].z;
double Cx = bx - ax, Cy = by - ay, Cz = bz - az;
double Bx = cx - ax, By = cy - ay, Bz = cz - az;
double B2 = ax*ax - cx*cx + ay*ay - cy*cy + az*az - cz*cz;
double C2 = ax*ax - bx*bx + ay*ay - by*by + az*az - bz*bz;
double CByz = Cy*Bz - Cz*By;
double CBxz = Cx*Bz - Cz*Bx;
double CBxy = Cx*By - Cy*Bx;
double zz1 = - (Bz - Cz*Bx/Cx) / (By - Cy*Bx/Cx);
double z01 = - (B2 - Bx/Cx*C2) / ((By - Cy*Bx/Cx) * 2);
double zz2 = - (zz1*Cy + Cz) / Cx;
double z02 = - (z01*Cy*2 + C2) / (Cx * 2);
cen.z = - ((z02 - ax) * CByz - (z01 - ay) * CBxz - az * CBxy) / (zz2 * CByz - zz1 * CBxz + CBxy);
cen.x = zz2 * cen.z + z02;
cen.y = zz1 * cen.z + z01;
r = dis(cen, v[i]);
for(int l=0; l<k; l++) {
if(dis(cen, v[l]) <= r) continue;
double x1 = v[i].x, x2 = v[j].x, x3 = v[k].x, x4 = v[l].x;
double y1 = v[i].y, y2 = v[j].y, y3 = v[k].y, y4 = v[l].y;
double z1 = v[i].z, z2 = v[j].z, z3 = v[k].z, z4 = v[l].z;
double a11 = x2 - x1, a12 = y2 - y1, a13 = z2 - z1;
double a21 = x3 - x2, a22 = y3 - y2, a23 = z3 - z2;
double a31 = x4 - x1, a32 = y4 - y1, a33 = z4 - z1;
double det = a11 * (a22*a33 - a23*a32) - a12 * (a21*a33 - a23*a31) + a13 * (a21*a32 - a22*a31);
double c11 = a22*a33 - a32*a23, c12 = - (a12*a33 - a32*a13), c13 = a12*a23 - a22*a13;
double c21 = - (a21*a33 - a31*a23), c22 = a11*a33 - a31*a13, c23 = - (a11*a23 - a21*a13);
double c31 = a21*a32 - a31*a22, c32 = - (a11*a32 - a31*a12), c33 = a11*a22 - a21*a12;
double xx = x2*x2 - x1*x1 + y2*y2 - y1*y1 + z2*z2 - z1*z1;
double yy = x3*x3 - x2*x2 + y3*y3 - y2*y2 + z3*z3 - z2*z2;
double zz = x4*x4 - x1*x1 + y4*y4 - y1*y1 + z4*z4 - z1*z1;
cen.x = (c11*xx + c12*yy + c13*zz) / (det * 2);
cen.y = (c21*xx + c22*yy + c23*zz) / (det * 2);
cen.z = (c31*xx + c32*yy + c33*zz) / (det * 2);
r = dis(cen, v[i]);
}
}
}
}
if(abs(cen.x) < 1e-4) cen.x = 0;
if(abs(cen.y) < 1e-4) cen.y = 0;
if(abs(cen.z) < 1e-4) cen.z = 0;
// cout << cen.x << " " << cen.y << " " << cen.z << "\n";
cout << r << "\n";
}
백준 BOJ 6567번 : Let it Bead
문제 난이도 : Platinum V
알고리즘 분류 : 조합론, 번사이드 보조정리
N개의 원형으로 배치된 구슬을 M개의 색을 이용하여 칠하고, 이들을 회전시키거나 뒤집었을 때 같은 색 배치인 것은 동일한 것으로 판단할 때 가능한 조합이 몇 개인지 구하는 문제이다.
번사이드 보조정리에 대해서 배울 수 있는 연습 문제이다.
원리는 다음과 같다.
어떤 원형의 구슬의 조합으로 가능한 것을 하나 만들었다고 할 때, 예를 들어 이것이 RBRB로 2칸 회전시켰을 때마다 동일한 형태가 나온다면 중복을 제거하지 않고 2번 count 되도록 해준 뒤, 마지막에 N = 4로 나누어 한 번만 count 되도록 하는 것이다. (RBRB에서 2번, BRBR에서 2번 count 되고 이것을 4로 나누면 RBRB 1개만 count가 되므로 옳게 세어졌다는 것을 알 수 있다.)
다만 이 문제는 여기서 끝이 아니라 뒤집었을 때 같은 것도 동일한 것으로 판단하므로, 뒤집은 형태까지 모두 고려해주되 2N번씩 count 되도록 해주어야 한다.
따라서 뒤집었을 때 동일한 것 = 대칭이어야 하므로 대칭 형태인 것들의 개수를 세어주어서 총 count에 이것들까지 중복이 되도록 더해준 뒤 2N으로 나누어 답을 구해야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N, M; cin >> M >> N;
if(N == 0 && M == 0) break;
int ans = 0;
for(int i=1; i<=N; i++) ans += pow(M, __gcd(N, i));
if(N % 2 == 0) ans += (N / 2) * (pow(M, N/2) + pow(M, N/2 + 1));
else ans += N * pow(M, (N + 1)/2);
ans /= (N * 2);
cout << ans << "\n";
}
}
백준 BOJ 2261번 : 가장 가까운 두 점
문제 난이도 : Platinum II
알고리즘 분류 : 기하학, 분할 정복
2차원 좌표 평면 위에 N개의 점이 주어질 때, 가장 가까운 두 점 사이의 거리의 제곱을 구하는 문제이다.
가장 먼 두 점은 컨벡스 헐 + 회전하는 캘리퍼스로 구현이 가능하지만 가장 가까운 두 점은 어떻게 구할까?
방법은 바로 분할 정복을 이용하는 것이다.
점들을 x 좌표를 기준으로 오름차순 정렬을 해준 뒤, 가운데 점을 기준으로 분할 정복을 통해 최소 거리의 점을 찾는다.
분할 정복을 통해 구하는 과정에서 왼쪽 그룹의 점과 오른쪽 그룹의 점을 각각 선택하여 얻어지는 거리는 확인하지 않았으므로, 현재까지 구한 최소 거리보다 중점으로부터 가까운 점들을 모두 벡터에 넣고 가능한 조합들을 모두 검사해본다.
이 때 시간 초과를 방지하기 위해 벡터에 저장된 점들을 y 좌표를 기준으로 정렬한 뒤 이중 for문을 돌리는 과정에서 두 점의 y 좌표의 차이가 Min 값 이상이 되면 즉시 break문을 사용하여 불필요한 값의 비교가 최소화되도록 해주어야한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, y; };
bool cmpx(s a, s b) {
if(a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
bool cmpy(s a, s b) {
if(a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int dis(s a, s b) {
return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}
vector<s> v;
int f(int l, int r) {
if(l == r) return LLONG_MAX;
if(l+1 == r) return dis(v[l], v[r]);
int m = (l + r) / 2;
int Min = min({dis(v[l], v[r]), f(l, m), f(m+1, r)});
vector<s> u;
int cen = v[m].x;
for(int i=l; i<=r; i++)
if(pow(v[i].x - cen, 2) < Min) u.push_back(v[i]);
sort(u.begin(), u.end(), cmpy);
for(int i=0; i<u.size(); i++)
for(int j=i+1; j<u.size(); j++) {
if(pow(u[i].y - u[j].y, 2) >= Min) break;
if(pow(u[i].x - u[j].x, 2) < Min) Min = min(Min, dis(u[i], u[j]));
}
return Min;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;
sort(v.begin(), v.end(), cmpx);
int ans = f(0, N-1);
cout << ans << "\n";
}
백준 BOJ 26003번 : Lowest Latency
문제 난이도 : 난이도 정보 없음
알고리즘 분류 : 정보 없음
0 ≤ x, y, z < 10^9인 점이 무작위로 10^5개가 주어질 때, 가장 가까운 두 점 사이의 거리를 구하는 문제이다.
이러한 상황에서는 어떻게 구해야할까?
위의 가장 가까운 두 점 문제와 같은 방법으로 분할 정복을 이용한 구현이 가능하겠지만, 3차원 상의 점들이기 때문에 구현이 훨씬 복잡할 것이다.
이 문제에서는 점의 위치가 무작위로 주어진다는 점에 주목해야 한다.
가장 간단한 해결책은 점의 위치가 무작위라는 것은 이들이 상당히 균일한 분포를 가지고 있고, 따라서 대략적으로 계산했을 때 넉넉잡아 답이 최소한 10^6은 넘어간다는 것이다.
따라서 점들을 x 좌표를 기준으로 정렬했을 때 v[i]와 v[i+1] ~ v[i+100] 정도만 비교해줘도 확률적으로 그 안에는 무조건 답이 있음을 유추할 수 있다는 것이다.
따라서 O(N log N) 시간에 정렬을 수행하고, O(100 N) 시간에 탐색을 수행할 수 있으므로 충분히 짧은 시간에 답을 구할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, y, z; };
bool cmp(s a, s b) {
return a.x < b.x;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(6);
int N; cin >> N;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y >> v[i].z;
sort(v.begin(), v.end(), cmp);
double ans = DBL_MAX;
for(int i=0; i<N; i++)
for(int j=i+1; j<i+100 && j<N; j++) {
double dis = sqrt(pow(v[i].x - v[j].x, 2) + pow(v[i].y - v[j].y, 2) + pow(v[i].z - v[j].z, 2));
ans = min(ans, dis);
}
cout << ans << "\n";
}
백준 BOJ 22940번 : 선형 연립 방정식
문제 난이도 : Gold I
알고리즘 분류 : 가우스 소거법
가우스 소거법을 이용하여 N차 선형 연립 방정식의 해를 구하는 문제이다.
비교적 최근 문제로 출제되었고 전에 가우스 소거법을 구현할 줄 몰라서 풀지 못했던 문제가 기억나서 생각난 김에 구현해보았다.
다음과 같이 구현하면 거의 최소한의 코드로 가우스 소거법을 구현할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int M = N + 1;
vector<vector<double>> v(N, vector<double>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
double d = v[i][i], c = v[j][i] / v[i][i];
for(int k=0; k<M; k++) {
if(j == i) v[j][k] /= d;
else v[j][k] -= c * v[i][k];
}
}
}
for(int i=0; i<N; i++) cout << v[i].back() << " ";
cout << "\n";
}
참고로 아직 주어진 행렬에 대해 RREF와 같은 꼴을 만들도록 하는 코드는 구현하지 못했는데, 가까운 시일 내에 구현해볼 수 있도록 노력해보겠다.
백준 BOJ 26017번 : Guessing Game
문제 난이도 : Platinum II
알고리즘 분류 : 2-SAT
7일동안 각각 d_i개의 대회가 열리고, N명의 사람들이 매일 각 대회들 중 하나를 골라 승패 여부를 예상할 때, 마지막 2일동안의 승패 예상만 가지고 N명의 사람들을 모두 이길 수 있는지 여부를 구하는 문제이다.
다른 사람들은 1개 이하로 맞추고, 마지막 줄에 주어진 2개의 예측이 모두 맞으면 조건을 만족한다.
2-SAT를 이용해 문제를 풀이하기 위해 N명 각각에 대해 7C2개의 조합을 가지고 하나가 맞으면 다른 하나가 틀리게 되도록 N x 7C2개의 조건식을 만들 수 있다.
동시에 마지막 줄에 주어진 2개의 예측이 a, b라고 할 때 이들 또한 2-SAT 식의 절에 들어가야 하므로 ~a → a와 ~b → b 식을 추가해준 뒤 2-SAT를 돌려주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;
stack<int> s;
vector<bool> ch;
int dfs(int x) {
nnum[x] = ++ncnt;
s.push(x);
int tmp = nnum[x];
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(nnum[y] == 0) tmp = min(tmp, dfs(y));
else if(!ch[y]) tmp = min(tmp, nnum[y]);
}
if(tmp == nnum[x]) {
vector<int> v;
ccnt++;
while(true) {
int y = s.top();
s.pop();
v.push_back(y);
ch[y] = true;
cnum[y] = ccnt;
if(y == x) break;
}
sort(v.begin(), v.end());
scc.push_back(v);
}
return tmp;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> add(8);
for(int i=1; i<=7; i++) {
cin >> add[i];
add[i] += add[i-1];
}
int M = add[7];
adj.resize(M*2);
for(int i=0; i<N; i++) {
vector<int> v(7);
for(int j=0; j<7; j++) {
cin >> v[j];
if(v[j] > 0) v[j] += add[j];
else v[j] -= add[j];
}
for(int j=0; j<7; j++)
for(int k=j+1; k<7; k++) {
int a = -v[j], b = -v[k];
if(a < 0) a = (-a)*2 - 2;
else a = a*2 - 1;
if(b < 0) b = (-b)*2 - 2;
else b = b*2 - 1;
int na, nb;
if(a % 2 == 0) na = a + 1;
else na = a - 1;
if(b % 2 == 0) nb = b + 1;
else nb = b - 1;
adj[na].push_back(b);
adj[nb].push_back(a);
}
}
for(int i=0; i<2; i++) {
int x; cin >> x;
if(x > 0) x += add[5+i];
else x -= add[5+i];
if(x < 0) x = (-x)*2 - 2;
else x = x*2 - 1;
int nx;
if(x % 2 == 0) nx = x + 1;
else nx = x - 1;
adj[nx].push_back(x);
}
nnum.resize(M*2);
cnum.resize(M*2);
ch.resize(M*2);
for(int i=0; i<M*2; i++)
if(nnum[i] == 0) dfs(i);
bool check = true;
for(int i=0; i<M; i++) {
if(cnum[i*2] == cnum[i*2 + 1]) {
check = false;
break;
}
}
if(check) cout << "possible\n";
else cout << "impossible\n";
}
백준 BOJ 26012번 : Breeding Bugs
문제 난이도 : Platinum III
알고리즘 분류 : 이분 매칭, 에라토스테네스의 체
N개의 수가 주어질 때 어떤 두 수를 골라도 그 합이 소수가 되지 않도록 하는 집합의 최대 크기를 구하는 문제이다.
2를 제외한 모든 소수는 홀수이므로, 수들을 짝수와 홀수로 나누어 최대 독립 집합의 크기를 구해주면 된다.
최대 독립 집합의 크기 = N - 최대 매칭이라는 공식이 있으므로, 이분 매칭으로 문제를 풀어주면 된다.
예외 처리로 2가 나오지 않으려면 1이 1개 이하로 집합에 포함되면 된다.
소수 판별을 빨리 하기 위해 에라토스테네스의 체를 이용해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;
bool f(int x) {
vis[x] = true;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
l[x] = y, r[y] = x;
return true;
}
}
return false;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int Max = 2e7;
vector<bool> p(Max, true);
p[1] = false;
for(int i=2; i*i<Max; i++)
for(int j=2; i*j<Max; j++) p[i*j] = false;
int N; cin >> N;
vector<int> v, u;
bool one = false;
while(N--) {
int x; cin >> x;
if(x == 1) {
if(!one) {
v.push_back(x);
one = true;
}
continue;
}
if(x % 2 == 1) v.push_back(x);
else u.push_back(x);
}
adj.resize(v.size());
for(int i=0; i<v.size(); i++)
for(int j=0; j<u.size(); j++)
if(p[v[i] + u[j]]) adj[i].push_back(j);
l.resize(v.size(), -1);
r.resize(u.size(), -1);
int match = 0;
for(int i=0; i<v.size(); i++) {
vis.clear();
vis.resize(v.size());
if(f(i)) match++;
}
int ans = v.size() + u.size() - match;
cout << ans << "\n";
}
백준 BOJ 26050번 : 수열의 합 2
문제 난이도 : Gold I
알고리즘 분류 : 정수론
주어진 N에 대해 N의 모든 약수 d1, ... , dk가 있을 때 a_n = (-1)^d1 + (-1)^d2 + ... + (-1)^dk라고 한다면 주어지는 s, t에 대해 a_s + ... + a_t의 값을 구하는 문제이다. 이 때 s, t ≤ 10^14이다.
s, t 범위가 크므로 O(sqrt(N)) 풀이를 찾아야 하는 문제이다.
먼저 a_1 + ... + a_N을 구하는 함수 f(N)를 구현하고 답은 f(t) - f(s-1)로 구해주면 된다.
약수 dk가 나타나는 횟수는 N / dk를 내림한 값이므로, (-1)^dk × (N / dk)의 시그마 값을 구해주면 된다.
원래 이렇게 풀면 O(N) 시간에 풀이가 가능한데, 시간을 더 줄여야한다.
발견할 수 있는 성질은 N의 약수는 O(sqrt(N)) 시간에 구할 수 있을 정도로 적으므로, N / dk 값들의 종류도 O(sqrt(N)) 시간에 구할 수 있다.
따라서 각 N / dk 값이 변화하는 구간을 찾고, 이 구간의 길이만큼의 값을 한번에 구해줄 수 있다.
자세한 내용은 아래의 풀이 코드를 참고하면 쉬울 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int f(int N) {
vector<int> v, u;
for(int i=1; i*i<=N; i++) {
if(v.empty() || N/i != v.back()) {
v.push_back(i);
if(i != N/i) u.push_back(N/i);
}
}
for(int i=u.size()-1; i>=0; i--) v.push_back(u[i]);
int sum = (-1) * N;
for(int i=1; i<v.size(); i++) {
if((v[i] - v[i-1]) % 2 == 0) continue;
sum += (v[i] % 2 == 0 ? 1 : -1) * (N / v[i]);
}
return sum;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
int ans = f(b) - f(a-1);
cout << ans << "\n";
}
백준 BOJ 13738번 : Ghostbusters 2
문제 난이도 : Platinum II
알고리즘 분류 : 2-SAT, 이분 탐색
N개의 지점이 주어지고, 각 지점에서 상하 또는 좌우로 길이 x인 선분을 발사하여 같은 축에 있는 선분이 서로 겹치지 않게 하기 위한 x의 최댓값을 구하는 문제이다.
x를 임의로 정하고 서로 겹치는 것이 발생할 수 있는지를 검사하는 것은 가능하므로, 이분 탐색으로 접근하면 된다.
각 x에 대해서는 선분을 가로로 발사하면 true, 세로로 발사하면 false라고 생각하면 2-SAT 문제가 된다.
예를 들어 같은 가로축에 위치한 두 지점에 대해, 두 지점의 거리가 2x 이하이면 지점 a에서의 선분을 좌우로 선택했을 때 지점 b에서의 선분은 반드시 상하로 선택해야 하므로 a → not b가 되고, 마찬가지로 not b → a가 된다.
이런 식으로 여러 개의 절을 세워서 2-SAT 문제로 풀어주어 만약 가능한 상태가 존재한다면 l = m+1로, 그렇지 않다면 r = m-1로 설정하며 가능한 최댓값을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;
stack<int> s;
vector<bool> ch;
int dfs(int x) {
nnum[x] = ++ncnt;
s.push(x);
int tmp = nnum[x];
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(nnum[y] == 0) tmp = min(tmp, dfs(y));
else if(!ch[y]) tmp = min(tmp, nnum[y]);
}
if(tmp == nnum[x]) {
vector<int> v;
ccnt++;
while(true) {
int y = s.top();
s.pop();
v.push_back(y);
ch[y] = true;
cnum[y] = ccnt;
if(y == x) break;
}
sort(v.begin(), v.end());
scc.push_back(v);
}
return tmp;
}
struct st { int x, y; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<st> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i].x >> v[i].y;
int l = 0, r = INT_MAX, ans = 0;
while(l <= r) {
int m = (l + r) / 2;
adj.clear(); adj.resize(N*2);
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
int a = i, b = j;
if(a < 0) a = (-a)*2 - 2;
else a = a*2 - 1;
if(b < 0) b = (-b)*2 - 2;
else b = b*2 - 1;
int na, nb;
if(a % 2 == 0) na = a + 1;
else na = a - 1;
if(b % 2 == 0) nb = b + 1;
else nb = b - 1;
if(v[i].x == v[j].x && abs(v[i].y - v[j].y) <= m*2) {
adj[a].push_back(nb);
adj[b].push_back(na);
}
if(v[i].y == v[j].y && abs(v[i].x - v[j].x) <= m*2) {
adj[na].push_back(b);
adj[nb].push_back(a);
}
}
nnum.clear(); nnum.resize(N*2);
cnum.clear(); cnum.resize(N*2);
ch.clear(); ch.resize(N*2);
scc.clear();
ncnt = ccnt = 0;
for(int i=0; i<N*2; i++)
if(nnum[i] == 0) dfs(i);
bool check = true;
for(int i=0; i<N; i++) {
if(cnum[i*2] == cnum[i*2 + 1]) {
check = false;
break;
}
}
if(check) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
if(ans < INT_MAX) cout << ans << "\n";
else cout << "UNLIMITED\n";
}