코딩하는 두꺼비

www.acmicpc.net/problem/3020

많은 사람들이 lower_bound와 upper_bound함수를 사용해 이분탐색 알고리즘을 사용해 푼 것을 문제를 맞추고 나서 알 수 있었다.

난 처음엔 그냥 완탐으로 풀려다 시간 초과가 발생하는 바람에  누적합 알고리즘과 비슷하게 문제를 풀 수 있었다.

1. 석순과 종유석 벡터를 각각 생성 후 장애물이 마지막으로 지나는 부분의 벡터 값을 증가시켜주었다.(상한선 하한선 생성)

2. 그 후 크기가 1인 석순은 크기가 2인 석순을 지날 때 똑같이 부셔야 하므로 벡터의 모든 값을 갱신해주었다.

3. 마지막으로 두개의 벡터를 더한 값을 새로운 벡터에 넣어주고 그 벡터를 정렬 후 최소값과 그 갯수를 구할 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, h, x;
	cin >> n >> h;
	vector<int> v1(h + 1);
	vector<int> v2(h + 1);
	vector<int> v3;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (i % 2 == 1) {
			v1[x]++;
		}
		else {
			v2[h+1-x]++;
		}
	}
	for (int i = 1; i < h; i++) {
		v2[i + 1] += v2[i];
		v1[h - i] += v1[h + 1 - i];
	}
	for (int i = 1; i <= h; i++) {
		v3.push_back(v1[i] + v2[i]);
	}
	sort(v3.begin(), v3.end());
	int cnt = 1;
	for (int i = 1; i < v3.size(); i++) {
		if (v3[0] < v3[i]) {
			break;
		}
		cnt++;
	}
	cout << v3[0] << " " << cnt;
	return 0;
}

lower_bound와 upper_bound 함수를 좀 더 공부해서 다음번엔 써먹어 봐야겠다!(하지만 속도랑 코드 크기는 별차이 안남;;)

www.acmicpc.net/problem/2470

처음에 이분 탐색이라 생각하고 풀었는데 기본적인 이분탐색 구조와 살짝 다르게 구현해야해서 시간이 좀 걸린 문제이다.

반례를 보고 풀 수 있었는데 left = right인 경우에 같은 값이 출력되는 것을 생각 못하게 구현한 것이 패인이였다.

결국 기본적인 이분탐색과 다르게 left <= right형식과 mid를 사용하지 않아서 약간 변형된 문제였다.

또한 두 개의 용액만을 더해야 하기 때문에 투 포인터로 좀 애매할 것 같아 투 포인터를 사용하지 않았다.

1. 이분 탐색을 위해 벡터를 정렬한다.

2. 0과 가까운 것을 알기 위해 조건을 절댓값으로 비교해준다.

3. 합이 0보다 작으면 left증가 0보다 크면 right를 증가해서 값을 비교해주었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> v;

int main() {
	int n, x;
	long long ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = v.size() - 1;
	ans = v[left] + v[right];
	int ans1 = left;
	int ans2 = right;
	while (left < right) {
		long long sum = v[left] + v[right];
		if (abs(ans) > abs(sum)) {
			ans = sum;
			ans1 = left;
			ans2 = right;
		}
		if (sum > 0) {
			right -= 1;
		}
		else {
			left += 1;
		}

	}
	cout << v[ans1] << " " << v[ans2];
	return 0;
}

www.acmicpc.net/problem/1477

이분 탐색 문제를 몇개 풀어본 지라 나름 자신있게 도전을 했었다.

근데 우선 순위 큐를 사용해서 풀 수도 있을 것 같아 계속 하다보니 도저히 답을 구할 수 없었다.

그래서 결국 이분 탐색으로 풀려하는데 풀이법이 생각이 안나 다른 사람의 풀이를 결국 참고했다ㅠㅠ

예전에 풀었던 입국심사 문제와 조금 비슷한 면이 있는 문제 였는데 너무 생각없이 문제를 접근했던 것 같다.

다음 부턴 문제를 풀고 나서 확실히 이해하고 기억하는 습관을 길러야겠다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;

int main() {
	int n, m, l, x;
	cin >> n >> m >> l;
	v.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	v.push_back(l);
	
	int left = 1;
	int right = l - 1;
	int mid = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		int store = 0;
		for (int i = 1; i < v.size(); i++) {
			int d = v[i] - v[i - 1];
			store += d / mid;
			if (d % mid == 0) {
				store--;
			}
		}
		if (store > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << left;
	return 0;
}

참고한 블로그: paris-in-the-rain.tistory.com/44

딱 깔끔하게 푸셔서 도움이 많이 되었다..