대엉코딩

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

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

2. 주의사항

- 조건으로 인한 시간초과

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}

www.acmicpc.net/problem/3079

1. 풀이방법

- 일단, 문제를 보시면 M (친구들의 수) 가 매우 큽니다

- M배열같은경우 원소 하나씩 처리 (뭐 친구를 한명씩 심사대에 넣어본다거나)

- 이렇게 선형탐색만 해도 시간초과가 날 것입니다.  --> 이런방식은 안됨

- 그럼 주어진 배열의 값들로 탐색하는 것이 아닌 최소시간과 최대시간을 가지고 시간이라는 요소를 가지고 

- 이분탐색을 수행합니다.

- 시간이 주어졌을때 (시간) / (각각의 심사대에서 걸리는 시간) 을 하면 몇명을 심사할 수 있는지가 나오고

- 이것들을 더했을 때 주어진 시간에서의 (총 심사가능인원수)가 나오는데 이 인원이

- 친구들의 수 M보다 크면 심사가 되는 것이므로 결과값과 비교를 통해 넣어주고 더 적은 시간으로 가능한지를

- 탐색하러 떠납니다.

2. 주의사항

- 이분탐색 문제가 익숙치 않아서 그런지 좀 생각하는데 시간이 걸리는 것 같습니다.

- 그래도 저번에 www.acmicpc.net/problem/2792 (보석상자) 문제를 풀고난 후 라 조금 수월했던 것 같습니다.

3. 나의코드

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

long long n, m,tmp;
vector<long long> commitarr;
long long resulttime=1e18;
void inputs() {
	cin >> n >> m; //n개의 심사대 , m 명의 친구들
	for (int i = 0; i < n; i++) {
		cin >> tmp; commitarr.push_back(tmp);
	}
}

void findtime(long long l, long long h)
{
	if (l > h) return;
	long long mid = (l + h) / 2;
	long long tmpsum = 0;
	for (int i = 0; i < n; i++) {
		tmpsum += (mid / commitarr[i]); //시간동안 각각의 심사대에서 심사가능인원
	}
	if (tmpsum >= m) {
		if (resulttime > mid) { resulttime = mid; } //더 적은시간으로 가능하면 갱신
		findtime(l, mid - 1);
	}
	else findtime(mid + 1, h);

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	sort(commitarr.begin(), commitarr.end());
	long long lowtime = 1; long long hightime = commitarr[n - 1] * m;
	//가장 오래걸리는 심사대에서 모두 받을 경우가 최대
	findtime(lowtime, hightime);
	cout << resulttime;
	return 0;
}

www.acmicpc.net/problem/2776

1. 풀이방법

- 시간제한은 2초 

- N,M 모두 최대 1,000,000 이므로 M배열의 각각의 원소에 대해 N배열을 선형탐색하면 시간초과가 발생

- N배열을 정렬하고 (c++ stl에서 제공하는 sort함수는 O(nlogn)을 보장해줍니다.

- 그후 M배열 각각의 원소로 N배열에 대해서 이분탐색을 진행 하시면 됩니다.

- 재귀, 반복문 다 구현 가능하며 저는 이 문제는 while문으로 구현하였습니다.

2. 주의사항

- 시간초과

3. 나의코드

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



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t, n, m;
	cin >> t;
	while (t--) {
		cin >> n;
		vector<int> narr(n);
		for (int i = 0; i < n; i++) cin >> narr[i];
		sort(narr.begin(), narr.end()); // 정렬

		cin >> m;
		vector<int> marr(m);
		for (int i = 0; i < m; i++) cin >> marr[i];

		for (int i = 0; i < m; i++) { //수첩 2
			int lowindex = 0; int highindex = n - 1;
			while (1) {
				if (lowindex > highindex) { cout << 0<<"\n"; break;}
				int midindex = (lowindex + highindex) / 2;
				if (narr[midindex] == marr[i]) {cout << 1 << "\n"; break;}

				if (narr[midindex] > marr[i]) {
					highindex = midindex - 1;
				}
				else {
					lowindex = midindex + 1;
				}
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/2792

1. 풀이방법

- 구현 문제를 많이 풀다보니 이런문제를 처음 봤을 때, 조금 당황스러웠습니다...;

- 어쨋든 최소질투심을 유발하게끔 나눠주는 방법은 1과 최대보석의 수 중에 있을 것이니까

- 이분 탐색을 통해 그것을 탐색해가면서 mid의 값이 아이들에게 조건에 맞게 나누어 줄 수 있는지 확인.

- 나누어 줄 수 있으면 더 작은 질투심을 유발할 수 있는 값이 있는지 mid보다 작은 쪽을 탐색.

- 아니라면 mid보다 큰 쪽을 탐색.

- 최소값을 출력하여 주었습니다.

2. 주의사항

- 없음.

3. 나의코드

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

long long n, m;
long long numarr[300001];
long long result = 1e18;

bool canspread(long long mid) {
    long long num = 0;
    for (int i = 0; i < m; i++) {
        num += numarr[i] / mid;
        if (numarr[i] % mid) num++;
    }
    return n >= num;
}
int main() {
    cin >> n >> m;
    long long left = 1; long long right = 0;
    for (int i = 0; i < m; i++) {
        cin >> numarr[i];
        if (right < numarr[i]) right = numarr[i];
        }
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (canspread(mid)) {
            if (result > mid) result = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << result << "\n";
    return 0;
}

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

요즘 프로젝트로 biginteger를 다루는 자료형을 만들었었는데

이것의 부작용인지..... 문제를 처음 봤을때 조건들의 숫자가 그렇게 크지 않다고 생각하고 아무렇게나 접근했었는데

위와 같이 큰 수부터 1씩 감소 시켜주면서 잘라서 개수를 비교하여 처음  N 과 같아질때의 수를 출력하는 식으로 했더니?

채점중 2퍼인가 에서 시간초과...5퍼인가?.....

꽤 채점이 되다가 시간초과가 떳으면 이 코드에서 시간을 줄여보고자 생각을 했을 수도 있겠지만

터무늬 없어서 방법을 바꿔야 한다는 것을 깨닫고 문제 조건을 다시 파악했다....

무엇이 좋을까 하다가 떠오른건 "이분탐색"

코드의 디테일 까지는 잘 생각이 안나서 짜면서 신경 써야되는 부분이 있지만

역시 개념자체는 배워놓으면 잘 까먹지 않고 생각 나는 것 같아서 혼자 뿌듯....

이분 탐색으로 짠 코드는 다음과 같다.

간단해서 따로 설명할 것은 없어보이고 

길이는 1이상 이기때문에 처음 bottom값을 0으로 설정하면 채점중 런타임 에러가 나타난다. <주의>