급하게임개발

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

이 문제는 그리드를 이용한 dfs이다 즉 dfs의 탐색방향을 그리디를 통해 정해주게 되는것이다 우리는 오른쪽 부터 왼쪽으로 파이프를 순서대로 연결할건데 이때 파이프는 오른쪽 ,오른쪽 아래 ,왼쪽 아래 이렇게 만 움직일수있는데 우리가 오른쪽부터 파이프를 놓는데 진행중에 왼쪽 방향으로 탐색을 진행하게되면 파이프가 쭉 왼쪽으로 가면서 다른애들의 연결을 막게된다 왼쪽부터 탐색할거면 반대로 놓아도 되긴 한다

#include<iostream>
using namespace std;
int R, C;
int arr[10001][501];
int cnt = 0;
int dr[3] = { -1, 0, 1 };
int dc[3] = { 1, 1, 1 };
bool canGo(int r, int c) {
	if (!arr[r][c] && r >= 0 && r < R && c >= 0 && c < C)
		return true;
	else
		return false;
}
bool dfs(int r, int c) {
	if (c== C - 1) {
		cnt += 1;
		return true;
	}
	else {
		arr[r][c] = 1;
		for (int i = 0; i < 3; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (canGo(nr, nc)) {
				if (dfs(nr, nc)) {
					return true;
				}
			}
		}
		return false;
	}
}
int main() {
	cin >> R >> C;
	string inputStr;
	for (int i = 0; i < R; i++) {
		cin >> inputStr;
		for (int j = 0; j < C; j++) {
			if (inputStr[j] == '.')
				arr[i][j] = 0;
			else
				arr[i][j] = 1;
		}
	}

	for (int i = 0; i < R; i++) {
		dfs(i, 0);
	}

	cout << cnt;
	return 0;
}

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

이 문제의  경우 풀이는 매우 쉽다.

우리는 중계기를 설치  할건데 이 중계기의 빈공간의 합이 최소가 되게 고르면 된다 그이유는 일단 중계기는 어떠한 점이 아닌 직선형의 중계기 이다 

빈 공간은 무조건 우리가 설치한 센서들의 갯수인 n-1 개 만 설치가 된다

즉 이 n-1개의 빈공간 들중 우리는 가장 큰 영역을 제외해주어야 한다 근데  센서 2개로 영역을 고른다고 가정 할 때 우리가 결국 포기해야하는 영역들 중 이영역을 k개로 나누기 위해서는 결국 k-1개의 공간은 포기를 해야한다

#include <iostream>
#include <algorithm>
#include <vector>
int n, k;
using namespace std;
vector<int> sensors;
vector<int> spaces;
int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		sensors.push_back(tmp);
	}

	sort(sensors.begin(), sensors.end());
	int beforeSensor = sensors[0];
	for (int i = 1; i<sensors.size(); i++) {
		spaces.push_back(sensors[i] - beforeSensor);
		beforeSensor = sensors[i];
	}
	
	sort(spaces.begin(), spaces.end());

	int sum = 0;
	
	for (int i = 0; i < (int)spaces.size() -  (k-1); i++) {
		sum += spaces[i];
	}

	cout << sum;
}

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

이 문제는 처음에 그리디를 어떤 방식으로 짜는지가 문제 풀이의 핵심이다

처음에 나는 숫자가나온 갯수에 따라 그리디를 선택 했지만
1700 에서 사용하는 스케줄링 방식은 가장 오랫동안 안쓰는 원소를 교체하는 방식으로 그리디를 작성 한다
이에 큐를 사용하여 나오는 위치를 저장해주고 이를 이용해서 비교해줌으로서 값을 출력하는 방식을 사용했다

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int arr[100];
int concent[100];
queue<int> useCount[101];
bool isUsed[100] = { 0, };
int main() {
	int cnt = 0;
	int input = 0;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		useCount[arr[i]].push(i);
	}
	int i = 0;
	while (input < n && i < k) {
		if (!isUsed[arr[i]]) {
			isUsed[arr[i]] = true;
			concent[input] = arr[i];
			useCount[arr[i]].pop();
			i++;
			input++;
		}
		else {
			useCount[arr[i]].pop();
			i++;
		}
	}
	if (n > k) {
		cout << 0;
		return 0;
	}

	else {
		for (int j = i; j < k; j++) {
			int willPlug = arr[j];
			useCount[arr[j]].pop();
			int outConcnet=-1;
			int notUse=0;
			bool isIn = false;
			for (int l = 0; l < n; l++) {
				if (concent[l] == willPlug) {
					outConcnet = l;
					isIn = true;
					break;
				}
				
			}
			if (!isIn) {
				for (int l = 0; l < n; l++) {
					if (useCount[concent[l]].empty()) {
						outConcnet = l;
						break;
					}
					if (notUse < useCount[concent[l]].front()) {
						notUse = useCount[concent[l]].front();
						outConcnet = l;
					}
				}
			}
			if (concent[outConcnet] != willPlug) {
				concent[outConcnet] = willPlug;
				cnt += 1;
			}
		}
	}

	cout << cnt;
}

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

이 문제는 그리디이다 이문제는 얼피하면 그냥 정렬한후 처리처리 하게 하는거로 생각해서 틀릴 수가 있다 이문제의 경우 최소의 해를 그리디로 만족 시키기위해서는 큰 화물을 처리할 수 있는 화물은 최대한 큰것 부터 처리 해야한다는 것이다
백준에서 제공 하는 3번 input을 이용해서 보자

이렇게 테스트 케이스가 주어졌을때
Krane 을 처리 할 수 있는 무게에 따라 오름 차순 정렬해주면
23 25 28 32 이렇게 정렬이 된다
이제 화물을 오름 차순으로 정렬해보자
2 5 7 10 16 18 20 24 27 32 이렇게 정렬이 된다.

이후 3번째 크레인이 처리 할수 있는 최대 무게는 32 임으로 해당 크레인은 일단 32를 처리 한다
2번 째크레인은 27을 처리하고 1번째 크레인은 24를  0번째 크레인은 23을 처리한다
이렇게 처리하면 1초가 지나간다

그 후 크레인은 내가 현재 보고있는 화물이 이미 처리되어있으면 다음 화물을 처리하기 위해서 내가 지금 있는 위치에서 이전 위치까지 탐색하다 화물이 안처리되었으면 처리하면 된다 이렇게 로직이 가능한 이유는 오름차순 정렬을 했기 때문에 내가 처리한 화물 이전에 있는 화물들은 다처리 할 수 있기 때문이다

코드는 아래와 같다

#include<iostream>
#include<algorithm>
using namespace std;
int krane[50];
int cargo[10000];
int kraneidx[50];
bool isDo[10000];
// 각 Krane이 처리할수 있는 최대 무게의 index저장
int clear;
int n, m;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin>>krane[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin>>cargo[i];
	}
	sort(krane, krane + n);
	sort(cargo, cargo + m);
	if (krane[n - 1] < cargo[m - 1]) {
		cout << -1;
		return 0;
	}
	int maxKrane = n - 1; 
	for (int i = m - 1; i >= 0; i--) {
		if (maxKrane < 0)
			break;
		if (krane[maxKrane] >= cargo[i]) {
			kraneidx[maxKrane] = i;
			maxKrane--;
		}
	}
	for (int i = 0; i <= maxKrane; i++) {
		kraneidx[i] = -1;
	}
	int cnt = 0;
	maxKrane = kraneidx[n - 1];
	while (maxKrane > 0) {
		maxKrane = kraneidx[n - 1];
		for (int i = n - 1; i >= 0; i--) {
			if (kraneidx[i] < 0)
				continue;
			if (!isDo[kraneidx[i]]) {
				isDo[kraneidx[i]] = true;
			}
			else {
				while (isDo[kraneidx[i]] && kraneidx[i]>=0) {
					kraneidx[i] -= 1;
				}
				if(kraneidx[i] >= 0)
					isDo[kraneidx[i]] = true;
			}
		}
		if (kraneidx[n - 1] < 0)
			break;
		cnt += 1;
	}
	cout << cnt;
}

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

이 문제는 그리디 문제이다 처음에 이문제를 완전 탐색으로 하려 했으나 완전 탐색을 하라고 낸 문제는 아닌거 같았다 이에 s->t 를 하기보다는 t->s 를 해야겠다고 생각했다 이에 끝문자가 A면 단순 Pop을 B면 Pop을 하고 뒤집어주었다

#include <iostream>
#include<string>        
#include<algorithm>
using namespace std;
int main() {
	string s, t;
	cin >> s;
	cin >> t;
	while (1) {
		if (s.size() == t.size()) {
			if (t == s) {
				cout << 1;
			}
			else {
				cout << 0;
			}
			break;
		}
		if (t[t.size() - 1] == 'A') {
			t.pop_back();
		}
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}
}

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

이 문제는 전형 적인 그리디 문제이다 그리디 문제의 특징은 모든 과정에서의 답이아니기 때문에 풀 수 있다

이문제는 일단 주의 할점을 일반적으로 input을 받으면 int 형자료형은 50만자리의 수를 받을 수없기 때문에 string으로 input을 받아 사용하는게 좋다

또한 이문제는 스택을 두고 이전에 들어온 값들보다 현재 들어오는 값들을 뽑고 거기에 넣으면서 뽑은 횟수를 저장해야한다 그래서 만약에 최대 뽑기수보다 못뽑으면 그냥 그상태로 값이 나온다

#include<iostream>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
stack<long long> bigStack;
stack<long long> answerStack;
long long n, k;
string num;
vector<long long> arr;
long long popCount=0;
long long result = 0;
int main() {
	cin >> n >> k;
	cin >> num;
	for (int i = 0; i < num.length(); ++i) {
		arr.push_back(num[i] - '0');  // 문자 '0'을 빼서 실제 숫자로 변환
	}

	if(arr.size()!=0)
		bigStack.push(arr[0]);
	for (long long i = 1; i < n; i++) {
		while (!bigStack.empty()&& bigStack.top() < arr[i] && popCount<k) {
			bigStack.pop();
			popCount += 1;
		}
		bigStack.push(arr[i]);
	}
	while (popCount < k) {
		bigStack.pop();
		popCount += 1;
	}
	while (!bigStack.empty()) {
		answerStack.push(bigStack.top());
		bigStack.pop();
	}

	while (!answerStack.empty()) {
		cout << answerStack.top();
		answerStack.pop();
	}

}

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

이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의  곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
	priority_queue<int> plusNum;
	priority_queue<int,vector<int>, greater<int>> negativeNum;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp1;
		cin >> temp1;
		if (temp1 > 0) {
			plusNum.push(temp1);
		}
		else {
			negativeNum.push(temp1);
		}
	}
	int sum = 0;
	while (!plusNum.empty())
	{
		int num1, num2;
		num1 = plusNum.top();
		plusNum.pop();
		if (plusNum.empty()) {
			sum += num1;
			break;
		}
		num2 = plusNum.top();
		plusNum.pop();

		if (num1 != 1 && num2 != 1) {
			sum += num1 * num2;
		}
		else {
			sum += num1 + num2;
		}
	}
	while (!negativeNum.empty())
	{
		int num1, num2;
		num1 = negativeNum.top();
		negativeNum.pop();
		if (negativeNum.empty()) {
			sum += num1;
			break;
		}
		num2 = negativeNum.top();
		negativeNum.pop();
		sum += num1 * num2;

	}

	cout << sum;

}

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

이 문제의 경우 Priority Queue를 사용하지 않으면 시간 초과 가 발생한다 이문제의 핵심은 작은 가방에 담을수 있는 가장 큰걸 담고 그다음크기의 가방에 그 가방의 크기에  담을 수 있는것중 가장 큰것을 담으면 된다.  
이 로직을 구현하기 위해서는 일차적으로 가장 작은 무게에 담을 수 있는 모든 물건들을 선택한다 거기서 가장 큰 애를 선택한다. 이차적으로 이전에 담고 남은 물건들중에 두번째 무게에 담을 수 있는 모든 물건들을 모두 고른 후 이전 애 고른애들과 합쳐서 놓은 다음 그중에 큰거를 고르면 된다.

이 로직에서 일단 필요한건 우선순위 큐다. 일차적으로 가방을 작은 순으로 나열해서 가장 작은 가방에 담을 수  있는 애를 우선순위큐에 담는다 보석들도 무게순으로 정렬 되어 있다 그래서 첫번째 가방에 담으면 첫번째 가방에 담긴 마지막 인덱스 이후로 무게가 큰 보석들이 남는다 그중 두번째 가방에 닿을 수 있는 물건들을 담아서 우선순위 큐에 넣는다. 거기서 최고 큰값을 선택 한다

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue<int> pq;
int bag[300000];
pair<int, int> jewerly[300000];

int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		jewerly[i] = { temp1,temp2 };
	}

	for (int i = 0; i < k; i++) {
		cin >> bag[i];
	}

	sort(jewerly, jewerly + n);
	sort(bag, bag + k);

	int idx=0;
	long long sum = 0;

	for (int i = 0; i < k; i++) {
		while (idx < n && bag[i] >= jewerly[idx].first) {
			pq.push(jewerly[idx].second);
			idx++;
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum;
}