solved.ac class 5 밀기 (1)
05 Oct 2021
A. 벡터 매칭
평면 상 점이 N개 주어지고, 두점을 이어서 벡터를 만들 때, 벡터의 합의 길이의 최소값을 구하는 문제입니다. 점이 N개가 주어 진다면, 벡터의 개수는 총 N/2 입니다. N=2k이라 하면 (N이 홀수 일때는 N-1=2k)라 하면, k개의 점은 더해지고, k개의 점의 좌표는 빼집니다. (벡터는 한 점에서 다른 점을 빼는 것이기 때문에)
그래서 $\sqrt{(x_1+x_2+..+x_k-x_{k+1}-..-x_{2k})^2+(y_1+y_2+….+y_k-y_{k+1}-…{y_{2k})^2}}$ 으로 벡터합의 길이를 나타낼 수 있습니다.
$2k \choose k$ 의 경우의 수가 나오고 2k의 최대값 20일때 1847560 정도가 나오므로 만족합니다. 이를 구현하면 됩니다. 모든 경우의 수에 대한 최소값을 구하면됩니다.
B. 보석 도둑
보석 N개에 대해 각 보석 당 무게와 가격이 주어지고, 가방 k개에 대해 각 가방이 담을 수 있는 총 무게가 주어집니다. 가방에 최대 한개의 보석만 들어갈 수 있고, 훔칠 수 있는 보석 가격 합의 최댓값을 구하는 문제였습니다.
multiset 에 가방 무게를 담고(무게가 중복가능하니), 보석의 무게와 가격을 우선순위 큐에 넣고, 보석을 가격에 대해 내림 차 순으로 정렬을 했습니다. 가장 비싼 보석 부터 lower_bound를 이용하여 담을 수 있는 가장 작은 가방에 담아주었습니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n,k;
cin>>n>>k;
priority_queue<pi,vector<pi>>v;
multiset<int>bag;
for(int i=0;i<n;i++){
int p1,p2;
cin>>p1>>p2;
v.push({p2,p1});
}
for(int i=0;i<k;i++){
int p1;
cin>>p1;
bag.insert(p1);
}
ll ans =0;
while(!v.empty()){
int cost = v.top().first;
int weight = v.top().second;
v.pop();
auto it = bag.lower_bound(weight);
if(it==bag.end())
continue;
bag.erase(it);
ans+=cost;
}
cout<<ans<<endl;
return 0;
}
C. 냅색문제
N개의 물건과 최대 C 만큼의 무게를 넣을 수 있는 가방 하나가 주어질때, N개의 물건을 가방에 넣는 방법의 수를 구하는 문제입니다. 모든 부분 집합 중 그 합이 C와 같거나 작은 부분집합의 개수를 세면 됩니다.
N≤40이므로 $O(2^n)$은 시간초과가 나지만 N/2≤20 은 $O(2^n)$ 을 해도 시간 초과가 나지 않습니다. 절반을 나눠서 부분집합의 합을 구한 뒤, 두 경우를 모두 고려하면 됩니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
multiset<int>ms;
int arr[31];
int n,c;
void knapsack(int st,int en,ll sum,vector<ll>&v){
if(st>en) {
v.push_back(sum);
return;
}
knapsack(st+1,en,sum,v);
knapsack(st+1,en,sum+arr[st],v);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>c;
for(int i=0;i<n;i++){
cin>>arr[i];
}
ll ans = 0;
vector<ll>l;
vector<ll>r;
knapsack(0,n/2,0,l);
knapsack(n/2+1,n-1,0,r);
sort(r.begin(),r.end());
for(auto i : l){
ll tmp = c-i;
ll pos = upper_bound(r.begin(),r.end(),tmp)-r.begin();
ans += pos;
}
cout<<ans;
return 0;
}
D. 부분수열의 합 2
N개의 정수로 이루어진 수열이 주어지고, 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제였습니다.(1≤N≤40). O(2^N)은 시간초과가 납니다.
냅색문제 처럼 반으로 쪼개서 문제를 풀면 됩니다. lower_bound,upper_bound를 이용해서 해당 수와 같은 개수를 세어 주었습니다. knapsack 함수에 있는 flag문은 하나로 넣은 경우에만 벡터에 삽입하도록 사용했습니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
multiset<int>ms;
int arr[41];
int n,s;
void knapsack(int st,int en,ll sum,vector<ll>&v,bool flag){
if(st>en) {
if(flag)
v.push_back(sum);
return;
}
knapsack(st+1,en,sum,v,flag);
knapsack(st+1,en,sum+arr[st],v,true);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>s;
for(int i=0;i<n;i++){
cin>>arr[i];
}
ll ans = 0;
vector<ll>l;
vector<ll>r;
knapsack(0,n/2,0,l,false);
knapsack(n/2+1,n-1,0,r,false);
sort(r.begin(),r.end());
for(auto i : l){
auto a = lower_bound(r.begin(),r.end(),s-i);
auto b = upper_bound(r.begin(),r.end(),s-i);
ans+=(b-a);
if(i==s)
ans+=1;
}
auto a = lower_bound(r.begin(),r.end(),s);
auto b = upper_bound(r.begin(),r.end(),s);
ans+=(b-a);
cout<<ans;
return 0;
}
E. 세 수의 합
N개의 200,000,000 이하의 자연수로 이루어진 집합 U이 주어집니다. x+y+z=k 를 만족하는 원소 x,y,z,k 가 있을때, 최대 k를 찾는 문제입니다. x,y,z,k는 중복될 수 있습니다.
x ≤ y ≤ z ≤ k 라 가정하면 x+y = k-z 가 성립 됩니다. x+y와 k-z 같은 경우에 대해 x+y+z가 최대인 값을 구하면 되는 문제였습니다. N≤1,000이고, $O(n^2logn)$에 구현했습니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 9223372036854775807
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tup;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
bool cmp(ll a,ll b){
return a>b;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
set<ll>s;
int n;
cin>>n;
for(int i=0;i<n;i++){
ll p1;
cin>>p1;
s.insert(p1);
}
ll MAX = *s.rbegin();
ll ans = 0;
set<ll>s1;
map<ll,ll>mp;
for(auto i : s){
for(auto k:s){
s1.insert(k+i);
}
}
for(auto k:s){
for(auto z:s){
if(k<z)
continue;
if(mp.find(k-z)!=mp.end()){
if(mp[k-z]<z){
mp[k-z]=z;
}
}
else
mp[k-z]=z;
}
}
vector<ll>v;
for(auto i:s1){
if(mp.find(i)!=mp.end())
{
v.push_back(i+mp[i]);
}
}
sort(v.begin(),v.end(),cmp);
cout<<v.front()<<endl;
return 0;
}