삼분 탐색 알고리즘 문제 풀이 모음 220926
삼분 탐색 알고리즘(Ternary Search Algorithm)이란 말 그대로 구간에서 1/3 지점과 2/3 지점의 함수값의 크기 비교를 기반으로 탐색을 해나가는 알고리즘이다.
이분 탐색 알고리즘은 그래프가 단조 증가 또는 단조 감소한다는 조건 하에서만 사용이 가능하지만, 삼분 탐색은 극값이 최대 1개 이하로 있는 모든 그래프에 대하여 사용 가능하다. (즉, 단순히 극값을 갖는 그래프 뿐만이 아닌 단조 증가, 감소 그래프에서도 사용이 가능하다.)
1개의 최솟값을 갖는 y = x^2 꼴의 그래프를 [l, r]의 구간에서 삼분 탐색하는 상황에 대해 생각해보자. (물론 극값을 구간에 포함하고 있다고 가정한다.)
1/3 지점을 x = m1, 2/3 지점을 x = m2라고 하며, 우리는 극값의 x 좌표 x_min을 찾고자 한다. (그러면 f_min = f(x_min)으로 구할 수 있다.)
( i ) f(m1) > f(m2)일 경우, 최소한 [l, m1] 구간에는 극값을 포함하지 않는다. 따라서 l = m1으로 옮겨준다.
( ii ) f(m1) < f(m2)일 경우, 최소한 [m2, r] 구간에는 극값을 포함하지 않는다. 따라서 r = m2으로 옮겨준다.
위의 과정을 반복하면 구간이 수렴하고, 적절한 횟수만큼 반복을 시켜준 뒤 답을 도출해주면 된다.
이제 예제들을 풀어보면서 연습해보자.
백준 BOJ 11662번 : 민호와 강호
문제 난이도 : Gold IV
알고리즘 분류 : 삼분 탐색
민호가 (v0.x, v0.y)에서 (v1.x, v1.y)로 일정한 속도로 걸어가고, 강호도 (v2.x, v2.y)에서 (v3.x, v3.y)로 일정한 속도로 걸어가며 두 사람은 각자의 시작점에서 동시에 출발하여 각자의 도착점에 동시에 도착한다고 할 때, 두 사람의 거리가 최소일 때의 그 거리를 구하는 문제이다.
두 사람 사이의 거리 그래프가 극값을 1개 이하로 가지므로 삼분 탐색을 사용할 수 있다.
두 사람 사이의 거리를 매개 변수에 대해 나타낸 뒤, 거리의 최솟값을 찾아주면 된다.
예를 들어 t = 0 ~ 1 범위에서 민호의 위치를 나타내자면, (tx2 + (1-t)x1, ty2 + (1-t)y1)으로 나타낼 수 있다.
이건 선분에 대한 방정식을 매개변수로 표현하는 건데 고등학교 1학년 과정에 있는 것으로 기억한다.
이제 t = 0 ~ 1 범위에서 삼분 탐색을 해주면 된다.
다른 사람들의 풀이를 보니 바로 거리를 구해주는 방식으로 했던데 나는 이 방법이 편했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(8);
vector<s> v(4);
for(int i=0; i<4; i++) cin >> v[i].x >> v[i].y;
double l = 0, r = 1;
for(int tr=1; tr<=1e5; tr++) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
double a = sqrt(pow((m1*v[1].x + (1-m1)*v[0].x) - (m1*v[3].x + (1-m1)*v[2].x), 2)
+ pow((m1*v[1].y + (1-m1)*v[0].y) - (m1*v[3].y + (1-m1)*v[2].y), 2));
double b = sqrt(pow((m2*v[1].x + (1-m2)*v[0].x) - (m2*v[3].x + (1-m2)*v[2].x), 2)
+ pow((m2*v[1].y + (1-m2)*v[0].y) - (m2*v[3].y + (1-m2)*v[2].y), 2));
if(tr == 1e5) {
cout << a << "\n";
break;
}
else if(a < b) r = m2;
else if(a > b) l = m1;
}
}
백준 BOJ 8986번 : 전봇대
문제 난이도 : Platinum V
알고리즘 분류 : 삼분 탐색
1차원 선상에 위치한 N개의 전봇대 좌표가 주어질 때, 각각을 정수 좌표로 이동시켜 일정한 간격으로 만들기 위해 필요한 최소 이동 거리 합을 구하는 문제이다.
예를 들어 N = 4이고 좌표가 0, 4, 6, 9라면 두 번째 전봇대를 1만큼 이동시켜 0, 3, 6, 9로 만들 수 있고, 이 때 답은 1이다.
전봇대 사이의 거리를 x라고 할 때, 전봇대의 총 이동 거리를 f(x)라고 하자.
그러면 y = f(x) 그래프는 아래로 볼록한 그래프를 구성한다. (상식적으로 중간에 최솟값이 있으니까 당연하다.)
따라서 삼분 탐색을 사용할 수 있다.
이 문제가 위의 문제와 다른 점은 x가 정수 좌표에서만 정의가 된다는 것인데, 그래프의 개형 자체는 똑같으므로 비슷한 방식으로 풀어줄 수 있다.
대신 여기서는 x가 정수에서만 정의됨을 활용하여 탐색 종료 조건을 r - l < 3과 같이 설정해줄 수 있다.
#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;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int l = 0, r = v[N-1];
int tr = 1e4;
while(r - l >= 3) {
int m1 = (l*2 + r) / 3;
int m2 = (l + r*2) / 3;
int s1 = 0;
for(int i=0; i<N; i++) s1 += abs(m1*i - v[i]);
int s2 = 0;
for(int i=0; i<N; i++) s2 += abs(m2*i - v[i]);
if(s1 < s2) r = m2;
else if(s1 > s2) l = m1;
}
int ans = LLONG_MAX;
for(int i=l; i<=r; i++) {
int sum = 0;
for(int j=0; j<N; j++) sum += abs(i*j - v[j]);
ans = min(ans, sum);
}
cout << ans << "\n";
}
백준 BOJ 11664번 : 선분과 점
문제 난이도 : Silver I
알고리즘 분류 : 삼분 탐색
3차원 좌표평면 상에서 선분과 점 사이의 최소 거리를 구하는 문제이다.
벡터를 사용해서 풀어도 되고, 삼분 탐색을 이용해서 풀어도 된다.
여기서는 삼분 탐색을 연습하고 있으니 삼분 탐색으로 풀어보자.
위의 BOJ 11662와 마찬가지로, 매개변수를 이용하여 t = 0 ~ 1으로 선분의 내분점을 잡을 수 있다.
이러한 선분 위의 내분점과 점 사이의 거리를 이용하여 삼분 탐색을 해주면 풀이 가능하다.
참고로 f(m1) = f(m2)인 경우가 나올 수 있으므로 해당 경우에도 l = m1으로 옮기던가 r = m2로 옮기던가 둘 중 하나를 처리 해주어야 반례가 발생하지 않는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y, z; };
double f(s a, s 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(6);
vector<s> v(3);
for(int i=0; i<3; i++)
cin >> v[i].x >> v[i].y >> v[i].z;
double l = 0, r = 1, tr = 1e3;
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
double a = f({m1*v[1].x + (1-m1)*v[0].x, m1*v[1].y + (1-m1)*v[0].y, m1*v[1].z + (1-m1)*v[0].z}, v[2]);
double b = f({m2*v[1].x + (1-m2)*v[0].x, m2*v[1].y + (1-m2)*v[0].y, m2*v[1].z + (1-m2)*v[0].z}, v[2]);
if(tr == 0) cout << a << "\n";
else if(a > b) l = m1;
else r = m2;
}
}
백준 BOJ 13011번 : 사탕의 밀도
문제 난이도 : Silver I
알고리즘 분류 : 삼분 탐색
N명의 학생이 있고 각 바구니의 용량은 v[i], 원하는 사탕의 무게는 u[i]일 때 모든 학생들에게 동일한 밀도의 사탕을 줄 때 밀도를 얼마로 해야 각 참가자가 원하는 무게와 실제 무게의 차이가 최소가 되는지를 구하는 문제이다.
밀도를 먼저 가정하고 차이를 구한 뒤, 그 차이값에 따라 탐색 범위를 조정하는 삼분 탐색으로 풀이 가능하다.
무게 차이에 대한 연산을 여러 번 해야하기 때문에, 함수로 따로 빼서 구현하는 편이 나은 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
double f(vector<double> v, vector<double> u, double m) {
double sum = 0;
for(int i=0; i<v.size(); i++)
sum += abs(v[i] * m - u[i]);
return sum;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(9);
int N; cin >> N;
vector<double> v(N), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
double l = 0, r = 1e6;
double Min = INT_MAX, tr = 1e3;
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
double a = f(v, u, m1);
double b = f(v, u, m2);
if(tr == 0) cout << a << "\n";
else if(a > b) l = m1;
else r = m2;
}
}
백준 BOJ 3855번 : Trick or Treat
문제 난이도 : Gold IV
알고리즘 분류 : 삼분 탐색
우연인지 모르겠지만 이 문제도 사탕과 관련된 문제이다.
N개 지점의 (x,y) 좌표가 주어지고, y = 0 직선 위의 하나의 x 좌표를 잡아서 가장 먼 지점의 거리가 최소가 되게 할 때, 그 x 좌표를 구하는 문제이다.
가장 먼 거리가 최소가 되는 지점이 있으므로, 그래프는 아래로 볼록하므로 삼분 탐색을 이용해서 풀이 가능함을 알 수 있다.
x 좌표의 범위를 설정하고 그 범위 내에서 삼분 탐색을 수행해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y; };
double f(vector<s> v, double m) {
double Max = 0;
for(int i=0; i<v.size(); i++)
Max = max(Max, sqrt(pow(v[i].x - m, 2) + pow(v[i].y, 2)));
return Max;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(5);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;
double l = -2e5, r = 2e5, tr = 1e2;
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
double a = f(v, m1);
double b = f(v, m2);
if(tr == 0) cout << l << " " << a << "\n";
else if(a > b) l = m1;
else r = m2;
}
}
}
백준 BOJ 21618번 : Lunch Concert
문제 난이도 : Gold IV
알고리즘 분류 : 삼분 탐색
N명의 사람이 1차원 좌표 상에 있고, 각 사람의 위치와 단위 거리 1만큼을 이동하는데 걸리는 시간, 소리를 들을 수 있는 반경이 주어질 때 어떤 좌표에서 공연을 해야 모든 사람들이 공연을 듣는데 필요한 이동 시간의 합이 최소가 되는지를 구하는 문제이다.
일단 이동 시간의 합을 구하는 것은 어렵지 않고, 이를 함수로 만들어 둔다.
이동 시간의 합이 최소가 되는 위치를 기준으로 양방향으로 멀어질수록, 이동 시간의 합이 커짐을 알 수 있고 따라서 그래프는 아래로 볼록한 개형을 가지며 삼분 탐색을 사용하여 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, t, r; };
int f(vector<s> v, int m) {
int sum = 0;
for(int i=0; i<v.size(); i++) {
if(v[i].x - v[i].r <= m && m <= v[i].x + v[i].r) continue;
else if(m < v[i].x - v[i].r) sum += ((v[i].x - v[i].r) - m) * v[i].t;
else if(m > v[i].x + v[i].r) sum += (m - (v[i].x + v[i].r)) * v[i].t;
}
return sum;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].x >> v[i].t >> v[i].r;
int l = 0, r = 1e9, tr = 1e2;
while(tr--) {
int m1 = (l*2 + r) / 3;
int m2 = (l + r*2) / 3;
int a = f(v, m1);
int b = f(v, m2);
if(a > b) l = m1;
else r = m2;
}
int m = (l + r) / 2;
int ans = f(v, m);
cout << ans << "\n";
}
백준 BOJ 12742번, 12743번 : 혼합물 (Small), (Large)
문제 난이도 : Platinum IV
알고리즘 분류 : 삼분 탐색
A를 단위 질량만큼 만들기 위해 A_1 ~ A_N이 각각 v[i]만큼 필요하거나, 또는 B를 단위 질량만큼 만들기 위해 B_1 ~ B_N이 각각 u[i]만큼 필요하다고 할 때 A의 단위 질량 당 가격은 M이고 B의 단위 질량당 가격은 K일 때 최대로 만들 수 있는 물질의 비용과, 그 때 각 물질을 얼만큼씩 만들어야 하는지를 구하는 문제이다.
먼저 A를 만들 수 있는 최대 양 r을 찾고, l = 0일 때 [l, r] 범위 내에서 A를 만들고 나머지로 B를 최대한 만든다.
이제 만들어진 물질의 비용을 구할 수 있으며, 이 비용에 따라 삼분 탐색을 수행해주면 된다.
small, large 두 버전 모두 동일한 알고리즘으로 풀린다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
double M, K;
vector<double> v, u, w;
struct s { double a, b, c; };
s f(double m) {
double Min = LLONG_MAX;
for(int i=0; i<N; i++)
Min = min(Min, (w[i] - m * v[i]) / u[i]);
return {m * M + Min * K, m, Min};
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(2);
cin >> N >> M >> K;
v.resize(N);
u.resize(N);
w.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
for(int i=0; i<N; i++) cin >> w[i];
double l = 0, r = LLONG_MAX, tr = 1e2;
for(int i=0; i<N; i++) r = min(r, w[i] / v[i]);
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
if(f(m1).a < f(m2).a) l = m1;
else r = m2;
}
double m = (l + r) / 2;
cout << f(m).a << "\n";
cout << f(m).b << " " << f(m).c << "\n";
}
백준 BOJ 8983번 : 사냥꾼
문제 난이도 : Gold IV
알고리즘 분류 : 삼분 탐색
x축 위에 N개의 사대가 있고, M개의 동물들의 좌표 (a, b)가 주어진다.
사대와 동물 (a, b) 사이의 거리를 |x - a| + b라고 할 때, 거리가 K 이내인 모든 동물을 사냥할 수 있다고 한다면 한 개 이상의 사대에 대해 사정 거리 이내에 있는 동물들의 개수를 구하는 문제이다.
하나의 동물에 대해 사정 거리 이내에 있는지를, 가장 거리가 가까운 사대를 찾기 위해 삼분 탐색을 사용하여 풀 수 있다.
가장 가까운 사대를 찾았으면 그 사대와의 맨해튼 거리가 K 이내인지 체크하여 counting 해주면 된다.
#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, M, K; cin >> N >> M >> K;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
int ans = 0;
while(M--) {
int x, y; cin >> x >> y;
int l = 0, r = N-1, tr = 1e2;
while(tr--) {
int m1 = (l*2 + r) / 3;
int m2 = (l + r*2) / 3;
int d1 = abs(x - v[m1]) + y;
int d2 = abs(x - v[m2]) + y;
if(d1 > d2) l = m1;
else r = m2;
}
bool check = false;
for(int i=l; i<=r; i++)
if(abs(x - v[i]) + y <= K) check = true;
if(check) ans++;
}
cout << ans << "\n";
}
백준 BOJ 1087번 : 쥐 잡기
문제 난이도 : Platinum IV
알고리즘 분류 : 삼분 탐색
N개의 점의 좌표와 이동 속도가 주어질 때, 어떤 시점에서도 N개의 점이 하나의 정사각형의 내부에 동시에 포함되지 않도록 하는 가장 큰 정사각형의 한 변의 길이를 구하는 문제이다.
문제를 바꿔 말하면 N개의 점을 (정사각형의 변 위의 점까지 포함하여) 포함하는 최소 정사각형의 한 변의 길이를 구하는 문제이다.
따라서 시간 t일 때 점들의 x 좌표의 최대 최소 차이, y 좌표의 최대 최소 차이 중 큰 것을 삼분 탐색으로 구하면서 범위를 좁혀주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y, vx, vy; };
vector<s> v;
double f(double m) {
double xmin = INT_MAX, ymin = INT_MAX, xmax = INT_MIN, ymax = INT_MIN;
for(int i=0; i<v.size(); i++) {
xmin = min(xmin, v[i].x + v[i].vx * m);
ymin = min(ymin, v[i].y + v[i].vy * m);
xmax = max(xmax, v[i].x + v[i].vx * m);
ymax = max(ymax, v[i].y + v[i].vy * m);
}
return max(xmax - xmin, ymax - ymin);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(9);
int N; cin >> N;
v.resize(N);
for(int i=0; i<N; i++)
cin >> v[i].x >> v[i].y >> v[i].vx >> v[i].vy;
double l = 0, r = 2e3, tr = 1e2;
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
if(f(m1) > f(m2)) l = m1;
else r = m2;
}
double m = (l + r) / 2;
cout << f(m) << "\n";
}
백준 BOJ 17574번 : Jackpot
문제 난이도 : Gold IV
알고리즘 분류 : 삼분 탐색
N개의 문 중 하나의 뒤에 상금이 있고, 상금은 문을 열 때마다 줄어들며, 초기 상금이 m이고 주어진 상수 값이 f일 때 d개의 문을 연 상태에서 남은 상금의 값 pr = m - (d * f)^2이라고 하자.
예상 수익이 당첨 확률에 남은 상금을 곱한 값이라고 할 때 예상 수익을 극대화시키기 위해서는 문을 몇 개 연 상태에서 고르는 것이 최선인지를 구하는 문제이다.
문제에서 하라는 대로 식을 구해주기만 하면 된다.
d개의 문을 열었을 때 당첨 확률은 1/(N - d)이므로, 예상 수익은 1/(N-d) x (m - (d x f)^2)이다.
이것은 위로 볼록한 그래프 개형을 가지므로 (그려서 확인하지 않더라도 문제에서 준 "최댓값"을 구하라는 표현을 보면 극대값이 존재함을 예상할 수 있다.) 삼분 탐색으로 이를 찾아주기만 하면 된다.
다만 주의할 점은 문을 모두 연 상태는 제외해야 하므로 (왜냐하면 문을 "일부" 열고 나서 최종 선택을 하는 것이므로) r = N-1로 두어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
double N, M, K;
double f(double m) {
return (1.0 / (N - m)) * (M - pow(m * K, 2));
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(6);
cin >> N >> M >> K;
double l = 0, r = N-1, tr = 1e2;
while(tr--) {
double m1 = (l*2 + r) / 3;
double m2 = (l + r*2) / 3;
if(f(m1) < f(m2)) l = m1;
else r = m2;
}
double m = (l + r) / 2;
cout << f(m) << "\n";
}