대엉코딩

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;
}

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

1. 풀이방법

- N의 숫자의 범위가 큰편입니다.

- O(N^2)은 100,000,000 시간제한 0.5초에 타임리밋 걸릴 수 있습니다.

- 투포인터를 이용해 한번의 순회로 해결했습니다.

- 단, 이는 A[i]가 자연수 (음수 아님) 조건이 있기 때문에 사용할 수 있습니다.

2. 주의사항

- 문제 조건을 정확히 파악해야 합니다.

3. 나의코드

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

int N, M;
vector<long long> arr;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	long long tt;
	for (int i = 0; i < N; i++) {
		cin >> tt;
		arr.push_back(tt);
	}
	int tmpsum = arr[0];
	int resultcount = 0;
	int sp = 0;
	int ep = 0;
	while (1) {
		if (tmpsum == M) {
			resultcount++;
			tmpsum -= arr[sp];
			sp++;
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum < M) {
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum > M) {
			tmpsum -= arr[sp];
			sp++;
		}
	}
	cout << resultcount;
	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;
}

www.acmicpc.net/problem/1254

1. 풀이방법

- 일단 처음 문제를 읽고 든 생각은 제일 길어봤자 문자열의 길이 *2 정도 이겠구나 였습니다.

   (뒤에서부터 차례대로 추가하면 되니까)

- 입력은 string으로 받아 편의를 위해 저는 vector<char>에 옮겨 담았습니다.

- 그리고 이제 하나씩 추가를 하고 이게 펠린드롬이 맞는지를 확인하였습니다.

- 반복문만 활용하면 잘 풀 수 있는 문제였습니다.

2. 주의사항

- 없음. 

3. 나의코드

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

string s;
vector<char> carr;
vector<char> tmpc;
int resultlen;

bool isitpelen() {
	for (int i = 0; i < tmpc.size() / 2; i++) {
		if (tmpc[i] != tmpc[tmpc.size() - 1 - i]) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> s;
	for (int i = 0; i < s.length(); i++) carr.push_back(s[i]);

	resultlen = s.length();
	tmpc = carr;
	if (isitpelen()){
		cout << resultlen << "\n"; return 0;
	}
	for (int i = 0; i < s.length(); i++) {
		tmpc = carr;
		for (int j = i; j >= 0; j--) {
			tmpc.push_back(s[j]);
			if (isitpelen()) {
				cout << resultlen + i + 1 << "\n"; return 0;
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/6064

1. 풀이방법

 - M과N이 최대 4000씩입니다. 완전탐색의 경우 시간초과가 뜹니다

 - 멸망의 날 --> 이건 예시가 힌트를 주고 있는데 (10,12) 의 경우 60년이 종말의 년도 입니다

 - (두 수의 최소공배수)라는 게 잘 보이는 예시라서 금방 찾을 수 있었습니다.

 - 어떻게 해야 하나 고민을 하다가 x와y 는 문제에서 보면 M,N으로 증가율?이 나와있고 정해져 있으므로

 - <a,b>라고 할때 a나 b 중 하나를 x나 y 로 고정시켜도 증가율을 알고 있으므로 1씩 증가하며 탐색 시키지 않아도 

 - 알 수 있으므로 하나를 고정 시킵니다.

2. 주의사항

 - N을 넘어갈 때 0으로 초기화 되지 않고 1부터 초기화 되서 시작하므로

   (mod연산의 경우 0~N-1) 이므로 신경써서 MOD연산을 계산합니다

3. 나의코드

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

int T, M, N, x, y;

int GCD(int num1, int num2) { //최대 공약수
	if (num1%num2 == 0) return num2;
	return GCD(num2, num1%num2);
}
int LCM(int num1,int num2){ //최소 공배수
	return (num1*num2) / GCD(num1, num2);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> M >> N >> x >> y;
		int resultyear = x;
		bool check = false;
		while (1) {
			if (resultyear > LCM(M, N)) { break; }
			if (((resultyear-1)% N) +1 == y) { check = true; break; }
			resultyear += M;
		}
		if (check == true) { cout << resultyear << "\n"; }
		else { cout << -1 << "\n"; }
	}
	return 0;
}

www.acmicpc.net/problem/10815

1. 풀이방법

- 일단 문제 input사이즈를 보면 크다 500,000

- 만약 두번의 for문을 돌려서 탐색을 할경우 최악의경우 250,000,000,000 인데, 

- c++기준 대략 1초에 1억번의 연산을 한다고 가정하여도, 시간제한 2초를 훨씬 넘기 때문에 

- 선형탐색을 사용해서는 안된다 ----->이진탐색(binary search)를 사용하자.

- 오름차순으로 sorting을 한 후 시작한다.

2.주의사항

- 전형적인 이진탐색문제로서 이론을 그대로 코드로 옮겨주면 되겠다.

- 조건을 살짝씩 빼먹을 경우 무한루프에 자주 빠지니 조건을 꼼꼼하게 체크 해주자....>!

3. 나의코드

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

int N, M;
int Narr[500001];
int Marr[500001];

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> Marr[i];
	}
}
void bs(int start,int end,int searchnum) {
	int mid = (start + end) / 2;
	if (Narr[mid] == searchnum) { cout << 1 << " "; return; }
	if (mid >= end) { cout << 0 << " "; return; }
	if (Narr[mid] > searchnum) { bs(start, mid-1, searchnum); }
	if (Narr[mid] < searchnum) { bs(mid+1, end, searchnum); }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(Narr, Narr+N);
	for (int i = 0; i < M; i++) {
		bs(0, N - 1, Marr[i]);
	}
	return 0;
}