대엉코딩

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/2638

1. 풀이방법

- 문제를 보면 bfs를 이용해야 겠다는 생각이 들고,

- 처음에 딱 핵심이다 라고 생각되는 것은 0(빈칸) 중에서 외부공기 / 실내공기 를 나누어 주어야 한다는 것.

- 그리고 문제설정에서 외부공기는 반드시 존재하게끔 되어있습니다.

- 바로 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 적어도, 4자리는 외부공기라는 것

- 그래서 처음에 이 4점을 기준으로 bfs를 돌려 외부공기를 모두 2로 표시해주고 시작합니다.

- 저 같은 경우 벡터에 치즈의 자리를 모두 넣은 뒤, 이 치즈들이 사라질 때마다 이 자리들을 다시 큐에 넣어

- 이 치즈가 녹음으로써 내부공기 -> 외부공기 가 되는 것들을 체크해주었습니다.

2. 주의사항

- 이런 류의 문제에서 사라지는 c의 위치를 찾았을 때 바로 ground를 2로 바꿔버리면 그 뒤의 치즈들이 이 것에 의해

- 영향을 받을 수 있습니다. 그래서 벡터의서 check를 true로만 바꿔주고, 작업이 끝난뒤에

- check가 true인 것들을 한번에 2로 바꾸어주었습니다.

3. 나의코드

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

int n, m;
//1은 치즈 , 0 은 빈칸 , 2는 실외공기
int ground[101][101];
bool visited[101][101];
int cheesecount = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
struct cheese {
	int cx, cy;
	bool check;
};
vector<pair<int, int>> sideindex;
queue<pair<int, int>> tmpq;
vector<cheese> tmpv;

void inputs() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> ground[i][j];
			if (ground[i][j] == 1) {
				cheesecount++; tmpv.push_back({ i,j,false });
			}
		}
	}
	sideindex.push_back({ 0, 0 }); sideindex.push_back({ n - 1,0 });
	sideindex.push_back({ 0,m - 1 }); sideindex.push_back({ n - 1,m - 1 });
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m) return true;
	else return false;
}
void makeoutside() {
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (boundcheck(tx, ty) && visited[tx][ty] == false && ground[tx][ty] != 1) {
					visited[tx][ty] = true;
					tmpq.push({ tx,ty });
					ground[tx][ty] = 2;
				}
			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	int second = 0;		
	//실외공기 구하기
	for (int i = 0; i < 4; i++) {
		visited[sideindex[i].first][sideindex[i].second] = true;
		ground[sideindex[i].first][sideindex[i].second] = 2;
		tmpq.push(sideindex[i]);
	}
	
	makeoutside();
	while (1) {
		if (cheesecount == 0) break;
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) continue;
			int vsize = 0;
			for (int j = 0; j < 4; j++) { //4방향 탐색
				if (ground[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] == 2) {
					vsize++;
				}
				if (vsize >= 2) {
					cheesecount--;
					visited[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] = true;
					tmpv[i].check = true; //여기는 없어짐
					tmpq.push({ tmpv[i].cx + dx[j],tmpv[i].cy + dy[j] });
					break;
				}
			}
		}
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) {
				ground[tmpv[i].cx][tmpv[i].cy] = 2;
			}
		}
		makeoutside(); //없어진 치즈로 인해 실내공기에서 외부공기가 되는 녀석들 체크
		second++;
	}
	cout << second;
	return 0;
}

www.acmicpc.net/problem/1600

1. 풀이방법

- 약간은 어려워진 BFS인 것 같습니다.

- 체스의 나이트 처럼 이동할 수 있는 가능 횟수가 오직 K번 이므로, K번 + 나머지 횟수는 4방향탐색

- 을 통해 가야하는데 DFS로 구현을 할 경우 시간이 부족합니다.

- 그래서 BFS로 다시 짜는데, 핵심이라고 생각되는 것은 만약에 K번 중 한번을 사용하여 점프를 뛰고

- 바로 거기를 방문처리를 해버리면 4방향탐색을 통해 그쪽에 도착한 후 나중에 말 처럼 점프하는 사항을

- 고려할 수 가 없습니다.

- 그래서 평소 이용하는 visit 이차원 배열을 k의 수만큼 삼차원 배열로 만들어서

- k 중 몇번을 써서 왔는지를 확인하고 k번을 써서 i,j에 도착했을 경우 방문처리를 해줍니다.

- 만약 i,j로 왔는데 k를 한번도 사용하지 않고 왔다면 그 전에 i,j에 왔으나 k를 한번 써서 방문한 경우가 있어도

- 다시 큐로 들어가게끔 구현하였습니다.

2. 주의사항

- visit 처리

3. 나의코드

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

int k, w, h;
int chesspan[200][200];
bool visit[200][200][31]; //k는 0~30
int horsemovex[8] = { -1,-2,-2,-1,1,2,2,1 };
int horsemovey[8] = { -2,-1,1,2,2,1,-1,-2 };
int dx[4] = { 0,0,1,-1 }; //k번을 다 소모했을 경우
int dy[4] = { 1,-1,0,0 };
int s = 0;
int mincount = 99999999;
bool fail = false;
struct xyk {
	int x, y, kn,s;
};
queue<xyk> tmpq;

void inputs() { //1은 장애물
	cin >> k >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> chesspan[i][j];
		}
	}
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < h && y >= 0 && y < w) return true;
	else return false;
}
int bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			if (tmpq.empty()) { fail = true; return 0; }
			int nextx = tmpq.front().x;
			int nexty = tmpq.front().y;
			int nextk = tmpq.front().kn;
			int nexts = tmpq.front().s;
			tmpq.pop();
			if (nextx == h - 1 && nexty == w - 1) { 
				return nexts; }
			if (nextk != 0) {
				for (int i = 0; i < 8; i++) {
					int tx = nextx+ horsemovex[i]; int ty =nexty+ horsemovey[i];
					if (boundcheck(tx, ty) && visit[tx][ty][nextk-1] == false && chesspan[tx][ty] != 1) {
						tmpq.push({ tx,ty,nextk - 1,nexts +1 });
						visit[tx][ty][nextk-1] = true;
					}
				}
			}
			for (int i = 0; i < 4; i++) {
				int tx2=nextx +dx[i]; int ty2 =nexty+ dy[i];
				if (boundcheck(tx2, ty2) && visit[tx2][ty2][nextk] == false && chesspan[tx2][ty2] != 1) {
					tmpq.push({ tx2,ty2,nextk,nexts +1 });
					visit[tx2][ty2][nextk] = true;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	tmpq.push({ 0,0,k,0 });
	//출발점은 0,0 도착점은 h-1,w-1
	int r=bfs();
	if (fail == true) { cout << -1 << "\n"; }
	else cout <<r << "\n";


	return 0;
}

www.acmicpc.net/problem/15659

1. 풀이방법

- 일단 숫자는 고정이고, 연산자만으로 모든 순열을 다 짜고 연산을 시작한다.

- 문제는 연산자 우선순위에 따른 계산을 해야한다는 것인데

- 저 같은경우 * 또는 / 먼저 연산을 완료한 후 새로운 벡터에 넣어놓고 그 후 + 또는 - 연산을 해주었습니다.

- 이과정에서 구현이 매우 까다로웠는데,

- 먼저 해야하는 것은 * 또는 / 가 나오는 경우 이 연산자들이 연속되어있는 곳 까지는 연산을 계속해줍니다.

(예를 들어 5+7*4*3-3) 이런 경우 *가 처음 등장하면 뒤쪽에 -가 나오기 전까지는 쭉 연결해서 연산을 해줍니다.

- 그후 덧셈, 뺄셈 연산을 수행하는데, 예외사항들이 많아 너무 복잡한 문제였습니다. 개인적으로......

- 저 말고는 제 코드를 이해하는 분이 계실지가..ㅋㅋㅋㅋ

2. 주의사항

- 테스트케이스를 보면서 수정해나가면서 짠 후 ,, 90퍼에서 계속 실패가 떠서 예외사항을 직접 찾아 해매야 했습니다.

3. 나의코드

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

int N,tmp;
vector<long long> numarr;
vector<long long> oper;
vector<long long> tmpoper;
long long maxresult = -9999999999;
long long minresult = 9999999999;
bool allplusorminus;

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> tmp; numarr.push_back(tmp); }
	for (int i = 0; i < 4; i++) { cin >> tmp; oper.push_back(tmp); }
}

int makenum() {
	vector<long long> tmparr;
	int index = 0;
	for (int i = 0; i < tmpoper.size(); i++) { //곱셈 나눗셈 먼저
		if (tmpoper[i] == 2 || tmpoper[i] == 3) {
			int tempint=numarr[index];
			while (1) { //연속되는 곱셈,나눗셈까지는 모두 같이 처리
				if (i == tmpoper.size() || tmpoper[i] == 0 || tmpoper[i] == 1) { index++; break; }
				if (tmpoper[i] == 2) { //곱셈
					tempint *= numarr[index + 1];
					index++;
				}
				else { //나눗셈
					tempint /= numarr[index + 1];
					index++;
				}
				i++;
			}
			tmparr.push_back(tempint);
			i--;
		}
		else { //아래와 같이 생각해줘야할 예외사항이 너무 많다.!!!!!!!!!!!!!!!
			if (i==0 || i == tmpoper.size() - 1){ 
				tmparr.push_back(numarr[index]); index++;
				if (tmpoper.size() == 1) tmparr.push_back(numarr[index]);
			}
			if (i < tmpoper.size() - 1 && (tmpoper[i + 1] == 0 || tmpoper[i + 1] == 1)) { 
				tmparr.push_back(numarr[index]);
				index++;
			}
		}
	}
	long long result=tmparr[0];
	index = 1;
	for (int i = 0; i < tmpoper.size(); i++) {
		if (tmpoper[i] == 0 || tmpoper[i] == 1) {
			if (tmpoper[i] == 0) { // 덧셈
				result += tmparr[index];
				index++;
			}
			else { //뺄셈
				result -= tmparr[index];
				index++;
			}
		}
	}
	return result;
}

void makecase(int cnt) {
	if (cnt == N - 1) {
		/*cout << numarr[0];
		for (int i = 0; i < tmpoper.size(); i++) {
			if (tmpoper[i] == 0) { cout << " + "; }
			if (tmpoper[i] == 1) { cout << " - "; }
			if (tmpoper[i] == 2) { cout << " * "; }
			if (tmpoper[i] == 3) { cout << " / "; }
			cout << numarr[i + 1];
		}
		cout << "\n";*/
		if (makenum() > maxresult) { maxresult = makenum(); }
		if (makenum() < minresult) { minresult = makenum(); }
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (oper[i] != 0) {
			tmpoper.push_back(i);
			oper[i]--;
			makecase(cnt + 1);
			oper[i]++;
			tmpoper.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	makecase(0);
	cout << maxresult << "\n" << minresult << "\n";
	return 0;
}