대엉코딩

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

1. 풀이방법

- 문제가 요구하는 사항을 구현하는 문제인데, 스택을 이용해서 현재 몇개의 막대가 쌓여있는지를 확인하였습니다.

- 사실 굳이 STACK.SIZE()를 그냥 임의의 변수 하나를 만들어 관리하면 그냥 반복문만으로도 구현 가능합니다.

2. 주의사항

- 조각의 개수가 증가하는 경우는 두가지 경우입니다. 

- (1) 레이저가 자르는 경우 (2) 막대가 끝나는 경우

3. 나의코드

<stack이용>

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	stack<char> sarr;
	int resultnum = 0;
	for (int i = 0; i < s.length(); i++) {
		if (sarr.empty()) { //비어있을 경우
			sarr.push(s[i]); continue;
		}
		if (s[i] == ')'&&s[i-1]== '(') { //레이저
			sarr.pop();
			resultnum += sarr.size();
			continue;
		}
		if (s[i] == '(') { //막대의 시작
			sarr.push(s[i]);
		}
		else if (s[i] == ')') { //막대의 끝
			sarr.pop();
			resultnum++;
		}
	}
	cout << resultnum << "\n";
	return 0;
}

<변수로 관리>

#include<iostream>
#include<string>

	using namespace std;

	int main() {
		int cnt = 0, result = 0;
		string t;
		cin >> t;
		for (int i = 0; i < t.length(); i++) {
			if (t[i] == '(') {
				if (t[i + 1] == ')') {
					i++;
					result += cnt;
					continue;
				}
				cnt++;
			}
			else {
				cnt--;
				result++;
			}
		}
		cout << result;
		return 0;
	}

www.acmicpc.net/problem/17144

1. 풀이방법

- 온전한 구현문제 인 것 같습니다..

- 문제의 조건을 잘 파악하고 문제에서 원하는 대로 구현을 해주면 됩니다.

2. 주의사항

- 이 문제에서의 먼지가 퍼지는 것과 같이 가정상 한번에 쫙 퍼지는 것은 한좌표의 결과가 다른 좌표의 입력으로 들어가

   는 것을 조심해야 합니다.

- 저는 그래서 이전 단계의 좌표계 (roominfo)를 (copyroom)으로 복사해서 연산을 할 때는 copyroom으로 계산하고 결과를 roominfo에 넣었습니다.

3. 나의코드

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

int R, C, T;
int roominfo[51][51];
int copyroom[51][51];
int dx[4] = { 0,0,1,-1 }; //동서남북
int dy[4] = { 1,-1,0,0 };
int reverseclockx[4] = { 0,-1,0,1 }; //반시계
int reverseclocky[4] = { 1,0,-1,0 };
int clockx[4] = { 0,1,0,-1 }; //시계
int clocky[4] = { 1,0,-1,0 };
int dust;
vector<pair<int, int>> airfresh;

void inputs() {
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> roominfo[i][j];
			if (roominfo[i][j] == -1) {
				pair<int, int> tmpp; tmpp.first = i; tmpp.second = j;
				airfresh.push_back(tmpp);
			}
		}
	}
}

void dustmove() { //먼지이동
	for (int a = 0; a < R; a++) {
		for (int b = 0; b < C; b++) {
			if (roominfo[a][b] == -1) continue;
			int movedust = 0;
			for (int i = 0; i < 4; i++) {
				if (a + dx[i] < 0 || a + dx[i] >= R || b + dy[i] < 0 || b + dy[i] >= C) continue;
				if (roominfo[a + dx[i]][b + dy[i]] == -1) continue;
				roominfo[a + dx[i]][b+dy[i]] += copyroom[a][b] / 5;
				movedust++;
			}
			roominfo[a][b] -= (copyroom[a][b] / 5)*movedust;
		}
	}

}

void airclean() { //순환(공기청정)
	int dir = 0;
	int tmp,tmp2;
	int nextX = airfresh[0].first + reverseclockx[dir]; int nextY = airfresh[0].second + reverseclocky[dir];
	tmp = roominfo[nextX][nextY];
	roominfo[nextX][nextY] = 0;
	while (1) { //위쪽(반시계)
		if (nextX + reverseclockx[dir] == airfresh[0].first &&nextY + reverseclocky[dir] == airfresh[0].second) break; //공기 청정기를 만남
		if (nextX + reverseclockx[dir] == R || nextX + reverseclockx[dir] == -1 || nextY + reverseclocky[dir] == -1 || nextY + reverseclocky[dir] == C) { dir++; continue; }
		nextX += reverseclockx[dir]; nextY += reverseclocky[dir];
		tmp2 = roominfo[nextX][nextY];
		roominfo[nextX][nextY] = tmp;
		tmp = tmp2;
	}
	             //아래쪽(시계)
	dir = 0;
	nextX = airfresh[1].first + clockx[dir];  nextY = airfresh[1].second + clocky[dir];
	tmp = roominfo[nextX][nextY];
	roominfo[nextX][nextY] = 0;
	while (1) {
		if (nextX + clockx[dir] == airfresh[1].first &&nextY + clocky[dir] == airfresh[1].second) break;//공기 청정기를 만남
		if (nextX + clockx[dir] == R || nextX + clockx[dir] == -1 || nextY + clocky[dir] == -1 || nextY + clocky[dir] == C) { dir++; continue; }
		nextX += clockx[dir]; nextY += clocky[dir];
		tmp2 = roominfo[nextX][nextY];
		roominfo[nextX][nextY] = tmp;
		tmp = tmp2;
	}
}
void getdust() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (roominfo[i][j] > 0) dust += roominfo[i][j];
			}
		}
}
void copymap() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			copyroom[i][j] = roominfo[i][j];
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	for (int i = 0; i < T; i++) {
		copymap();
		dustmove();
		airclean();
	}
	getdust();
	cout << dust << "\n";
	return 0;
}