백준: Class 5 - 1007, 1202, 1208
</br>
클래스 5 계속
</br>
1007: 벡터 매칭
https://www.acmicpc.net/problem/1007
void func(int now, int d){
if( d == n/2 ){
ans = min(ans, (long long)sumx*sumx + (long long)sumy*sumy);
return;
}
for(int i = now+1; i < n; i++){
sumx -= 2*x[i];
sumy -= 2*y[i];
func(i, d+1);
sumx += 2*x[i];
sumy += 2*y[i];
}
}
// in main()
while( t-- ){
cin >> n;
sumx = 0, sumy = 0;
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
sumx += x[i];
sumy += y[i];
}
ans = LLONG_MAX;
for(int i = 0; i <= n/2; i++){
func(i-1, 0);
}
cout << sqrt(ans) << endl;
}
문제 이해하는 게 좀 힘들었는데
점들이 입력으로 주어지고, 얘네를 둘 씩 짝 지어서 각각 벡터(c++ 자료구조 벡터 아님)를 구한다
그 거리 벡터들을 다 더하면 마지막으로 벡터 하나가 나올 건데(x, y) 걔의 크기가 최소가 되는 애를 구해라
따라서 20C2 * 18C2 * … * 2C2겠네 어 근데 수가 너무 크다
그래서 좀 더 생각해 보니~~ 각각 벡터들을 구할 필요 없이 전체 합만 구하면 된다는 거다.
즉 n = 20이면, 10개를 골라서 걔네는 전체 합 중 +가 되는 부분일 거고, 나머지 10개는 -가 되는 부분일 거다
그럼 20C10 = 184756으로 가능하다.
일단 전체 벡터 합을 구하고, 거기서 -가 될 애들 n/2개를 골라서 걔네를 빼준다(이미 한 번 더해져 있으므로 2번 뺌)
그리고 n/2개를 다 골랐으면 답을 업데이트 하면 됨
</br>
1202: 보석 도둑
https://www.acmicpc.net/problem/1202
방법 1.
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2){
if( p1.second == p2.second )
return p1.first < p2.first;
return p1.second > p2.second;
}
// in main()
sort(gems.begin(), gems.end(), cmp);
sort(bags, bags+k);
long long ans = 0;
for(int i = 0; i < k; i++){
for(int j = 0; j < n; j++){
if( visited[j] == 0 && bags[i] >= gems[j].first ){
ans += gems[j].second;
visited[j] = 1;
break;
}
}
}
cout << ans << endl;
간단한 그리디다
일단 보석을 가치가 높은 것-무게가 작은 것 순으로 정렬하고, 가방을 무게가 작은 것 순으로 정렬해서 가능한 걸 담는다
O(NK)이기 때문에 300000^2라서 시간 초과 납니다
</br>
헉 그럼 어케 하지
방법 2.
priority_queue<P, vector<P>, cmp> gems;
for(int i = 0; i < n; i++){
int m, v;
cin >> m >> v;
gems.push(make_pair(m, v));
}
multiset<int> bags;
for(int i = 0; i < k; i++){
int b;
cin >> b;
bags.insert(b);
}
long long ans = 0;
while( gems.size() ){
if( bags.empty() ) break;
P g = gems.top();
gems.pop();
auto it = bags.lower_bound(g.first);
if( it != bags.end() ){
ans += g.second;
bags.erase(it);
}
}
cout << ans << endl;
set, map에 lower_bound() 이거 쓰면 된다
보기만 하고 써본 적은 딱히 없었는데 이번에 쓰게 됐네
말그대로 최소 저거인 위치를 반환한다. 이 보석을 담을 수 있는 최소의 가방을 고르면 되기 때문에 딱이다!!
auto it = lower_bound(bag.begin(), bag.end(), bound); // 1
auto it = bag.lower_bound(bound); // 2
참고로 1번은 O(N), 2번은 O(logN)에 동작하니 2번을 사용합시다
</br>
1208: 부분수열의 합 2
https://www.acmicpc.net/problem/1208
int n2 = n/2;
vector<int> left(1 << (n-n2));
for(int i = 0; i < (1 << (n-n2)); i++){
for(int j = 0; j < n-n2; j++){
if( i & (1 << j) ) left[i] += nums[j];
}
}
vector<int> right(1 << n2);
for(int i = 0; i < (1 << n2); i++){
for(int j = 0; j < n2; j++){
if( i & (1 << j) ) right[i] += nums[j+(n-n2)];
}
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int l = 0, r = right.size()-1;
long long ans = 0;
while( l < left.size() && r >= 0 ){
int sum = left[l] + right[r];
if( sum == s ){
int ll = left[l];
int rr = right[r];
long long cnt1 = 0, cnt2 = 0;
while( l < left.size() && left[l] == ll ){
l++;
cnt1++;
}
while( r >= 0 && right[r] == rr ){
r--;
cnt2++;
}
ans += cnt1*cnt2;
}
else if( sum < s ) l++;
else r--;
}
if( s == 0 ) ans--;
cout << ans << endl;
어렵다
다른 분의 코드를 보고 씀(https://jaimemin.tistory.com/1107)
일단 핵심은 모든 부분 수열을 보려면 2^40 = 1,099,511,627,776이므로, 시간 초과가 나기 때문에 수열을 반 반 나눠서, 2^20 = 1,048,576 두 개를 투 포인터로 확인하는 거다.
ex) 백준 예제
5 0
-7 -3 -2 5 8
-7 -3 | -2 5 8 // 반 나누기
0 -7 -3 -10 | 0 -2 5 8 3 6 13 11 // 각 수열 안에서 가능한 합 다 만들기
-10 -7 -3 0 | -2 0 3 5 6 8 11 13 // 정렬 후 투 포인터 사용
벡터에 부분합들 다 넣는 것도 신기했는데
int n2 = n/2;
vector<int> left(1 << (n-n2));
for(int i = 0; i < (1 << (n-n2)); i++){
for(int j = 0; j < n-n2; j++){
if( i & (1 << j) ) left[i] += nums[j];
}
}
vector<int> right(1 << n2);
for(int i = 0; i < (1 << n2); i++){
for(int j = 0; j < n2; j++){
if( i & (1 << j) ) right[i] += nums[j+(n-n2)];
}
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
부분 수열의 크기가 2^k개 이므로, 1을 시프트 해서 할당해 준다
i=0: 아무 것도 선택 x
i=1: j=0: left[1] += nums[0]
i=2: j=1: left[2] += nums[1]
i=3: j=0,1: left[3] += nums[0] + nums[1]
i=4: j=1: left[4] += nums[3]
이런 느낌이구나
똑똑한 방법들이 너무 많다
-7 -3 -2 | 5 8
0 -7 -3 -10 -2 -9 -5 -12 | 0 5 8 13
-12 -10 -9 -7 -5 -3 -2 0 | 0 5 8 13
참고로 위 코드는 반을 이렇게 나눔
int l = 0, r = right.size()-1;
long long ans = 0;
while( l < left.size() && r >= 0 ){
int sum = left[l] + right[r];
if( sum == s ){
int ll = left[l];
int rr = right[r];
long long cnt1 = 0, cnt2 = 0;
while( l < left.size() && left[l] == ll ){
l++;
cnt1++;
}
while( r >= 0 && right[r] == rr ){
r--;
cnt2++;
}
ans += cnt1*cnt2;
}
else if( sum < s ) l++;
else r--;
}
if( s == 0 ) ans--;
cout << ans << endl;
투 포인터 쪽이 오히려 더 쉽다
같은 게 있을 경우만 예외 처리 해 주면 된다
ex)
6 0
1 1 1 -1 -1 -1
1 1 1 | -1 -1 -1
1 1 1 2 2 2 3 | -3 -2 -2 -2 -1 -1 -1
1 1 1과 -1 -1 -1의 경우 3*3 = 9개 가능함
따라서 같은 것들의 개수를 세서 곱해주면 된다.
</br>
공부 많이 하자
</br>
댓글남기기