오늘의 문제
2295 세 수의 합
1654 랜선 자르기
18869 멀티버스 Ⅱ

2295 세 수의 합

코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr, two;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	arr = vector<int>(n, 0);
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());

	for (int i = 0; i < arr.size(); i++) {
		for (int j = i; j < arr.size(); j++) {
			two.emplace_back(arr[i] + arr[j]);
		}
	}
	sort(two.begin(), two.end());
	two.erase(unique(two.begin(), two.end()), two.end());

	for (int i = arr.size() - 1; i >= 0; i--) {
		for (int j = arr.size() - 2; j >= 0; j--) {
			if (binary_search(two.begin(), two.end(), arr[i] - arr[j])) {
				cout << arr[i];
				return 0;
			}
		}
	}
}

1654 랜선 자르기

코드

#include <bits/stdc++.h>
using namespace std;

long long k, n, arr[10002];

int count(int len) {
	long long cnt = 0;
	for (int i = 0; i < k; i++) {
		cnt += arr[i] / len;
	}
	return cnt;
}

int main() {
	cin >> k >> n;
	for (int i = 0; i < k; i++) cin >> arr[i];
	sort(arr, arr + k);
	long long s = 1, e = arr[k - 1];
	while (s < e) {
		long long mid = (s + e + 1) / 2;
		if (count(mid) >= n) s = mid;
		else e = mid - 1;
	}
	cout << s;
}

이런 문제를 Parametric Search라고 한다고 한다.

18869 멀티버스 Ⅱ

코드

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector < vector<int>> arr;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		vector<int> v;
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			v.emplace_back(a);
		}
		arr.emplace_back(v);
		sort(v.begin(),v .end());
		for (int j = 0; j < n; j++) {
			arr[i][j] = lower_bound(v.begin(), v.end(), arr[i][j]) - v.begin();
		}
	}
	int ans = 0;
	for (int i = 0; i < m - 1; i++) {
		for (int j = i + 1; j < m; j++) {
			bool same = true;
			for (int k = 0; k < n; k++) {
				if (arr[i][k] != arr[j][k]) {
					same = false;
					break;
				}
			}
			if (same) ++ans;
		}
	}
	cout << ans;
}

처음에는 그냥 인덱스 저장 후 정렬해서 순서대로 인덱스가 같은지 확인했는데, 이렇게 할 경우 10 10 / 20 10 을 같다고 처리한다! 그렇기 때문에 단순 정렬이 아닌 좌표 압축을 해서 lower_bound를 비교해야 한다.