중간에서 만나기 : 밋 인더 미들 알고리즘 풀이 모음 220821
백준 BOJ 16287번 : Parcel
문제 난이도 : Platinum V
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들), DP
N개의 물품 중 "서로 다른" 물품 4개를 골라 그 무게의 합이 M이 되도록 하는 경우가 있는지 확인하는 문제이다.
우선 N이 5,000이므로, O(N^4) 같은 방법은 안 된다.
각 원소는 최대 20만이므로, 두 원소의 합을 배열에 저장하고, 나머지 두 원소의 합을 배열의 기록을 이용하여 비교해보는 방식을 사용해볼 수 있다.
O(N^2) 시간에 두 원소의 합을 구성하는 원소의 주소를 u, w에 저장한다.
다음으로 O(N^2) 시간에 나머지 두 원소의 합이 기록된 것들 중에서 주소가 둘 다 겹치지 않는 것이 있으면, YES를 정답으로 출력해주면 되고 그러한 조합이 하나도 없을 경우 NO를 출력해주면 된다.
#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 M, N; cin >> M >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> u(5e5, -1), w(5e5, -1);
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) {
int sum = v[i] + v[j];
if(u[sum] != -1 || w[sum] != -1) continue;
u[sum] = i;
w[sum] = j;
}
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) {
int sum = M - (v[i] + v[j]);
if(sum <= 0 || sum >= 400000) continue;
if(u[sum] == -1 || w[sum] == -1) continue;
if(u[sum] == i || w[sum] == j || u[sum] == j || w[sum] == i) continue;
cout << "YES\n";
return 0;
}
cout << "NO\n";
}
백준 BOJ 10767번 : Palindromic Paths
문제 난이도 : Gold IV
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
N x N 배열이 주어질 때, 맨 왼쪽 위에서 맨 오른쪽 아래로 이동하면서 거친 알파벳들을 순서대로 합쳐 만들어진 문자열이 회문인 것의 종류의 수를 구하는 문제이다.
N이 최대 18이므로, 지나쳐야하는 경로의 길이는 최대 18 x 2 - 1 = 37이다.
O(2^37)은 시간 초과를 발생시키므로, 시간을 줄일 필요가 있다.
내가 생각한 풀이는 (i, N-1-i) 지점이 경로의 중간이 되므로, 모든 i에 대해 (i, N-1-i)에서 왼쪽 위로 가면서 만들어지는 문자열과 오른쪽 아래로 가면서 만들어지는 문자열이 같은지 검사하면 된다는 것이다.
이렇게 할 경우 O(2 x 2^17)로 시간을 단축시킬 수 있다.
이후 중복을 없애주기 위해서 벡터에 모두 넣은 뒤 정렬 및 중복 제거를 하여 마지막에 벡터에 남은 원소들의 수로 답을 찾아주었다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
vector<vector<char>> v;
vector<string> u, w;
void f(int x, int y, string s) {
if(x == 0 && y == 0) {
u.push_back(s);
return;
}
int dx[2] = {-1, 0};
int dy[2] = {0, -1};
for(int i=0; i<2; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0) continue;
f(nx, ny, s + v[nx][ny]);
}
}
void g(int x, int y, string s) {
if(x == N-1 && y == N-1) {
w.push_back(s);
return;
}
int dx[2] = {1, 0};
int dy[2] = {0, 1};
for(int i=0; i<2; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= N || ny >= N) continue;
g(nx, ny, s + v[nx][ny]);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
v.resize(N, vector<char>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<string> vv;
for(int i=0; i<N; i++) {
u.clear();
w.clear();
f(i, N-1-i, "");
g(i, N-1-i, "");
sort(u.begin(), u.end());
sort(w.begin(), w.end());
for(int j=0; j<u.size(); j++) {
if(upper_bound(w.begin(), w.end(), u[j]) - lower_bound(w.begin(), w.end(), u[j]) > 0) {
string s = u[j];
reverse(s.begin(), s.end());
vv.push_back(s + v[i][N-1-i] + u[j]);
}
}
}
sort(vv.begin(), vv.end());
vv.erase(unique(vv.begin(), vv.end()), vv.end());
cout << vv.size() << "\n";
}
백준 BOJ 9007번 : 카누 선수
문제 난이도 : Gold III
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
한 반에 N명씩으로 구성된 학생들의 몸무게가 주어질 때, 각 반에서 1명씩 뽑아 총 4명의 학생들의 몸무게의 합이 M과 가장 가깝게 하는 합을 구하는 문제이다. (이 때 M - x = y - M이라면 x를 선택한다.)
N이 1,000 이하이므로, 두 반씩 골라서 모든 가능한 몸무게의 조합을 두 개의 벡터에 저장한다.
그 다음 각 u[i]에 대해 M - u[i]에 가장 가까운 값을 w에서 이분 탐색으로 찾으면 O(N^2 log (N^2))에 풀 수 있다.
핵심은 "가장 가까운 합"을 어떻게 찾느냐는 것인데, 이것은 lower_bound로 찾은 주소와 그 주소 - 1 둘을 모두 체크해보아서 확인할 수 있다.
lower_bound가 x 이상인 최솟값이라면, lower_bound - 1의 값은 x 미만인 최댓값일 것이기 때문이다. (이터레이터라 주소와 개념이 다르긴 하지만 대충 이해하시면 됩니다..)
#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 T; cin >> T;
while(T--) {
int M, N; cin >> M >> N;
vector<vector<int>> v(4, vector<int>(N));
for(int i=0; i<4; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<int> u, w;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) u.push_back(v[0][i] + v[1][j]);
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) w.push_back(v[2][i] + v[3][j]);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = INT_MAX;
for(int i=0; i<u.size(); i++) {
int x = lower_bound(w.begin(), w.end(), M - u[i]) - w.begin();
if(x < w.size()) {
if(abs(u[i] + w[x] - M) < abs(ans - M)) ans = u[i] + w[x];
else if(abs(u[i] + w[x] - M) == abs(ans - M)) ans = min(ans, u[i] + w[x]);
}
if(x > 0) {
if(abs(u[i] + w[x-1] - M) < abs(ans - M)) ans = u[i] + w[x-1];
else if(abs(u[i] + w[x-1] - M) == abs(ans - M)) ans = min(ans, u[i] + w[x-1]);
}
}
cout << ans << "\n";
}
}
백준 BOJ 12045번 : Robot Rock Band (Large)
문제 난이도 : Gold III
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
4개의 그룹이 각각 N개의 값을 가졌을 때, 4개에서 각각 1개의 값들을 골라 xor한 값이 M인 조합의 수를 구하는 문제이다.
위의 카누 선수 문제와 동일하기 풀이하면 된다.
xor 연산의 경우 교환 법칙이 성립하므로 벡터 w에서 M ^ u[i] 값을 가지는 것의 개수를 이분 탐색으로 찾아주면 된다.
#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 T; cin >> T;
for(int t=1; t<=T; t++) {
int N, M; cin >> N >> M;
vector<vector<int>> v(4, vector<int>(N));
for(int i=0; i<4; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<int> u, w;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) u.push_back(v[0][i] ^ v[1][j]);
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) w.push_back(v[2][i] ^ v[3][j]);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = 0;
for(int i=0; i<u.size(); i++)
ans += upper_bound(w.begin(), w.end(), M ^ u[i]) - lower_bound(w.begin(), w.end(), M ^ u[i]);
cout << "Case #" << t << ": " << ans << "\n";
}
}
여담으로 이 문제를 풀면 백준 BOJ 12044번 : Robot Rock Band (Small)을 풀이할 수 있다.
백준 BOJ 23538번 : Easy Equation
문제 난이도 : Gold III
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
x^5 + y^4 + z^3 + w^2 + t = N을 만족하는 양의 정수 (x, y, z, w, t)의 순서쌍의 개수를 구하는 문제이다.
우선 x^5 + y^4 + z^3 + w^2 < N을 만족하기만 하면 t는 자동으로 결정된다.
그렇기 때문에 위 4개의 변수의 순서쌍을 구하는데에 초점을 맞추면 된다.
x^5 < N을 만족하는 x들과 w^2 < N을 만족하는 w들을 구해 x + w의 조합을 벡터 u에 저장한다.
y^4 < N을 만족하는 y들과 z^3 < N을 만족하는 z들을 구해 y + z의 조합을 벡터 w에 저장한다.
이렇게 나누는 이유는 u와 w의 size를 최대한 비슷하게 맞추기 위해서이다.
이제 밋 인더 미들로 조합의 수를 구할 수 있다.
#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<vector<int>> v(4);
for(int i=1; i*i*i*i*i<N; i++) v[0].push_back(i*i*i*i*i);
for(int i=1; i*i*i*i<N; i++) v[1].push_back(i*i*i*i);
for(int i=1; i*i*i<N; i++) v[2].push_back(i*i*i);
for(int i=1; i*i<N; i++) v[3].push_back(i*i);
vector<int> u, w;
for(int i=0; i<v[1].size(); i++)
for(int j=0; j<v[2].size(); j++)
u.push_back(v[1][i] + v[2][j]);
for(int i=0; i<v[0].size(); i++)
for(int j=0; j<v[3].size(); j++)
w.push_back(v[0][i] + v[3][j]);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = 0;
for(int i=0; i<u.size(); i++) {
ans += lower_bound(w.begin(), w.end(), N - u[i]) - w.begin();
}
cout << ans << "\n";
}
백준 BOJ 5526번 : ダーツ (Darts)
문제 난이도 : Gold II
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
4개 이하의 다트를 던져 N개의 점수 중 하나를 받고 그 합을 M점 이하의 최대한 가까운 점수로 만들려고 할 때, 그 점수를 구하는 문제이다.
위와 같이 밋 인더 미들로 풀이하면 되지만, 이 문제에서는 다트의 일부를 던지지 않아도 되므로, 벡터에 0을 추가해준다.
벡터에서 0이 선택된다면 그 다트는 던지지 않는 것으로 생각할 수 있기 때문이다.
이제 이분 탐색에서 x를 초과하는 최소 주소 - 1의 값을 검사해서 최댓값을 갱신해주면 된다.
#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; cin >> N >> M;
vector<int> v;
v.push_back(0);
for(int i=0; i<N; i++) {
int x; cin >> x;
v.push_back(x);
}
vector<int> u;
for(int i=0; i<v.size(); i++)
for(int j=0; j<v.size(); j++) u.push_back(v[i] + v[j]);
vector<int> w(u);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = 0;
for(int i=0; i<u.size(); i++) {
int x = upper_bound(w.begin(), w.end(), M - u[i]) - w.begin();
if(x == 0) continue;
ans = max(ans, u[i] + w[x-1]);
}
cout << ans << "\n";
}
백준 BOJ 10958번 : Ice Hockey World Championship
문제 난이도 : Gold I
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
N = 40 이하일 때, N개의 티켓의 가격의 합이 M원 이하가 되도록 하는 조합의 수를 구하는 문제이다.
한 개의 티켓도 사지 않는 경우도 경우에 포함된다.
N을 둘로 나누어 밋 인더 미들을 써주면 된다.
밋 인더 미들의 정석적인 문제라서 크게 설명할 부분은 없고 똑같이 풀이해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
vector<int> v, u, w;
void f(int idx, int sum) {
if(idx == N/2) {
u.push_back(sum);
return;
}
f(idx + 1, sum);
f(idx + 1, sum + v[idx]);
}
void g(int idx, int sum) {
if(idx == N) {
w.push_back(sum);
return;
}
g(idx + 1, sum);
g(idx + 1, sum + v[idx]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
f(0, 0);
g(N/2, 0);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = 0;
for(int i=0; i<u.size(); i++)
ans += upper_bound(w.begin(), w.end(), M - u[i]) - w.begin();
cout << ans << "\n";
}
백준 BOJ 6099번 : Exams
문제 난이도 : Gold IV
알고리즘 분류 : 중간에서 만나기 (밋 인더 미들)
N개의 각 시험에서 얻을 수 있는 점수가 주어질 때, 일부 시험을 선택하여 M점 이상의 점수를 만드는 경우의 수를 구하는 문제이다.
N이 36 이하이므로 밋 인더 미들을 사용하여 풀이할 수 있다.
0 ~ N/2까지 2^18 이하의 합으로 가능한 조합들을 모두 저장해주고, N/2 ~ N까지도 마찬가지로 해준다.
이제 벡터 값을 정렬 해주고 (한 쪽만 해주면 된다.) 각 2^18 조합에 대해 나머지 2^18 조합들은 이분 탐색으로 몇 개의 값이 조건을 충족하는지 구해서 더해주면 된다.
총 시간 복잡도는 O(2^(N/2) x (N/2))이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
vector<int> v, u, w;
void f(int idx, int sum) {
if(idx == N/2) {
u.push_back(sum);
return;
}
f(idx + 1, sum);
f(idx + 1, sum + v[idx]);
}
void g(int idx, int sum) {
if(idx == N) {
w.push_back(sum);
return;
}
g(idx + 1, sum);
g(idx + 1, sum + v[idx]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
f(0, 0);
g(N/2, 0);
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int ans = 0;
for(int i=0; i<u.size(); i++)
ans += w.end() - lower_bound(w.begin(), w.end(), M - u[i]);
cout << ans << "\n";
}
백준 BOJ 17637번 : Count Sqaures
문제 난이도 : Silver IV
알고리즘 분류 : 해시를 사용한 집합과 맵
N개의 수직선과 M개의 수평선이 그어졌을 때, 이들 중 4개를 선택하여 만들 수 있는 정사각형의 수를 구하는 문제이다.
즉, a_i - a_j = b_i - b_j의 쌍을 구하는 문제이다. (좌변의 i, j와 우변의 i, j는 다름)
map으로 a_i - a_j의 모든 쌍을 구해놓고, b_i - b_j들의 모든 쌍들에 대해 map에 몇 개의 값이 저장되어 있는지 확인하여 답에 더해주면 된다.
#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; cin >> N >> M;
vector<int> v(N), u(M);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<M; i++) cin >> u[i];
sort(v.begin(), v.end());
sort(u.begin(), u.end());
unordered_map<int, int> m;
for(int i=0; i<N; i++)
for(int j=0; j<i; j++) m[v[i] - v[j]]++;
int ans = 0;
for(int i=0; i<M; i++)
for(int j=0; j<i; j++) ans += m[u[i] - u[j]];
cout << ans << "\n";
}