급하게임개발

https://www.acmicpc.net/problem/1253

이 문제는 이분탐색 문제이다 처음 그냥 대충  쉽게 접근하다가 틀렸는데 같은수가 여러번 들어갈수 있음을 망각했다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long  n;
vector<long long > inputData;
int main() {
	cin >> n;
	long long  tmp;
	long long  cnt = 0;

	for (long long i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());

	for (long long i = 0; i < n; i++) {
		long long left = n-1;
		long long right = 0;
		
		while (right <n && left>=0  && right<left) {
			if (right == i) {
				if (right < n-1) {
					right += 1;
				}
			}
			if (left == i) {
				if (left > 0) {
					left -= 1;
				}
			}
			if (left == right) {
				break;
			}
			if ((inputData[right] + inputData[left]) == inputData[i]) {
				cnt += 1;
				break;
			}
			else if ((inputData[right] + inputData[left]) > inputData[i]) {
				left -= 1;
			}
			else if ((inputData[right] + inputData[left]) < inputData[i]) {
				right += 1;
			}
		}
	}
	cout << cnt;
}

전체 코드는 이렇게 된다 처음에는 2/n 기준으로 양옆으로 펼쳐지면서 값을 찾으려 했으나 이렇게 하면 못찾을 때 가 발생해서 양옆에서 조이는 방식으로 진행 했다

https://www.acmicpc.net/problem/12738

이 문제는 내가 투포인터에 넣어놓은 LIS 문제에 이분탐색 버전이다 이전에 어떠한 코테 시험에서 봤을 때 LIS를 투포인터로 풀어서 시간 초과가 히든 테케에서 발생했었는데 이 방식으로 풀었어야 한거 같다

백준 에서 제공 하는 해당 테스트케이스를 예로 들어보자

일단 LIS를 저장하는 LIS 배열이 있다고 생각하자.

LIS 배열이 비었을 때 10을 넣을 수 가 있다

이렇게 되어있는 상황에서 20을 넣는다고 가정할 때 현재 10만 들어가 있는 LIS에서 가장 큰원소이자 마지막 원소인 10보다 20이 크기 떄문에 LIS 배열의 다음 인덱스에 20을 넣어준다

자 그후 10을 넣으려고 보면 10이 들어갈 자리는 10 과 20중에 자기 와 같은 크기의 원소인 10밖에 없다
그럼 으로 해당 10을 최근에 10으로 바꾼다
그후 30을 넣게 되면

자 이과정을 반복하면 우리는 LIS의 크기를 구할 수 있다
이문제를 풀때의 핵심은
1. LIS 배열이 비었을 때 그냥 원소 넣기
2. LIS 에 있는 원소보다 현재 집어넣을 원소가 클때 끝에 넣기
3. LIS 에 마지막원소(가장큰 원소) 보다 작을 떄 이분탐색으로 들어가야 할 위치 찾아서 넣기

이렇게 하면 결국에 LIS 배열의 크기는 LIS의 크기만큼만  된다

#include <iostream>
using namespace std;
int n;
int arr[1000000];
int lis[1000000];
int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;

}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int j = 0;
	int i = 1;
	lis[0] = arr[0];
	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}
		i += 1;
	}
	cout << j + 1;
}

https://www.acmicpc.net/problem/3079

이 문제의 경우 아마도 프로그래머스 고득점 알고리즘 키트해도 비슷한 문제가 수록 되있을 것이다 단 백준에서는 매우 큰수까지의 비교를 하기 때문에 자료형에 unsinged long long을 해줌으로 범위를 널널 하게 잡아줘야 한다

이 문제의 경우는 각 테이블 마다 특정 시간을 주고 해당 시간 동안 몇명의 인원수를 상대할 수 있는 지를 더해서 친구들의 수와 같으면 정답이게 출력을 해주면 되지만 해당 조건을 만족하는 더 작은 수가 있을  수  있다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	unsigned long long n, m;
	vector <unsigned long long > times;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		unsigned long long tmp1;
		cin >> tmp1;
		times.push_back(tmp1);
	}

	sort(times.begin(), times.end());
	unsigned long long answer = 0;
	unsigned long min = 1;
	unsigned long long max = m * times.back();

	while (min <= max) {
		unsigned long long tmp = 0;
		unsigned long long avg = (min + max) / 2;
		for (unsigned long long i = 0; i < n; i++) {
			tmp += avg / times[i];
		}

		if (tmp < m) {
			min = avg + 1;
		}
		else {
			max = avg - 1;
			answer = avg;
		}
	}
	cout << answer;
}