급하게임개발

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

이 문제를 유니온 파인드와 그리디 로 풀려했는데 이상하게 계속 에러가 나서 그냥 유니온 파인드 안하고 순차로 검사하도록 바꾸니 정답이었다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int t, n, m;
bool check[1001];  // 책 배정 여부를 나타내는 boolean 배열

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

    cin >> t;
    while (t--) {
        cin >> n >> m;
        vector<pair<int, int>> students(m);

        // check 배열 초기화
        fill(check, check + n + 1, false);

        // 입력받기
        for (int i = 0; i < m; i++) {
            cin >> students[i].first >> students[i].second;
        }

        sort(students.begin(), students.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.second == b.second) return a.first < b.first;
            return a.second < b.second;
            });

        int cnt = 0;

        for (auto student: students) {
            int a = student.first;
            int b = student.second;
            for (int j = a; j <= b; j++) {  // a부터 b까지 탐색
                if (!check[j]) {  // 배정되지 않은 책이라면
                    check[j] = true;  // 책 배정
                    cnt++;
                    break;
                }
            }
        }

        cout << cnt << "\n";  // 정답 출력
    }

    return 0;
}

이 문제는 결국에 가장 책을 먼저 배정 하는게 목표이다 이에 b를 기준으로 오름 차순 해주고 b가 같다면 a를기준으로 오름차순 해주면서 결국에는 어떤 부분까지 책을 일찍 배정해줌으로서 배정해주는 문제이다

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

int n;
vector<bool> initial, target;

// 스위치를 누르는 함수
void pressSwitch(vector<bool>& bulbs, int index) {
    if (index > 0) bulbs[index - 1] = !bulbs[index - 1];
    bulbs[index] = !bulbs[index];
    if (index < n - 1) bulbs[index + 1] = !bulbs[index + 1];
}

// 전구를 바꾸는 함수 (첫 번째 전구를 누를지 여부 선택 가능)
int solve(bool pressFirst) {
    vector<bool> bulbs = initial;
    int count = 0;

    // 첫 번째 전구를 누르는 경우
    if (pressFirst) {
        pressSwitch(bulbs, 0);
        count++;
    }

    // 앞에서부터 필요한 곳만 스위치 누르기
    for (int i = 1; i < n; i++) {
        if (bulbs[i - 1] != target[i - 1]) {
            pressSwitch(bulbs, i);
            count++;
        }
    }

    // 결과 확인
    if (bulbs == target) return count;
    return INT_MAX;  // 불가능한 경우
}

int main() {
    cin >> n;
    initial.resize(n);
    target.resize(n);

    // 초기 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        initial[i] = (ch == '1');
    }

    // 목표 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        target[i] = (ch == '1');
    }

    // 두 가지 경우 비교
    int result = min(solve(false), solve(true));

    // 정답 출력
    if (result == INT_MAX) cout << -1;
    else cout << result;
}

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

이 문제를 풀 때 나는 현재 스위치를 기준으로 나와 양옆이 다르면 스위치를 누르려했으나 그게 아니었다 그냥 앞에서 부터 보면서 스위치를 기준으로 이전 전구가 다르면 스위치를 누르는데 0번스위치부터 할건지 1번스위치 부터 누를건지 2개의 경우의 수를 구해서 그중 최솟 값을 구하면 되는 거였다 0번스위치와 1번스위치로 나눈 이유는 0번 스위치의 값을 결정 할수 있는경우 지금 누르거나 다음에 누르거나 두가지 경우의수밖에없기 때문에 우리는 이전 상태를 비교함으로 0번스위치가 1일때의 시작과 0일때의 시작을 모두 비교해보는 것이다

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

이 문제는 그리드 문제이다 처음에는 input값을 받을 때 인덱스 값을 변경 시켜줬는데 이렇게 풀면틀렸었다
이문제는 일단 데드라인상으로 오름 차순 정렬해준후 이값을 컵라면수의 값에 대한 오름차순 prorityQueue로 만든다 그후  값을 넣어 주면서 현재 size즉 내가 선택한 문제수 가 dealine 값 즉 문제를 풀수 있는 시간보다 많아지면 문제를 포기해야하기 때문에 가장 작은 값을 가지는 값을 pop해준다

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

using namespace std;

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

    vector<pair<int, int>> problems(n);
    for (int i = 0; i < n; i++) {
        cin >> problems[i].first >> problems[i].second; // (데드라인, 컵라면 수)
    }

    // 1. 데드라인 기준 오름차순 정렬
    sort(problems.begin(), problems.end());

    // 2. 최소 힙 사용 (컵라면 개수가 적은 것을 우선 제거)
    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto& p : problems) {
        int deadline = p.first;
        int cupRamen = p.second;

        pq.push(cupRamen); // 현재 문제를 풀어본다고 가정하고 넣음

        // 3. 시간이 초과되면 가장 컵라면 개수가 적은 문제를 버림
        if (pq.size() > deadline) {
            pq.pop();
        }
    }

    // 4. 남아있는 문제들의 컵라면 개수 합산
    int ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }

    cout << ans << '\n';
    return 0;
}

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

이제 백준 티어가 3  넘어가면서 부터 알고리즘이 하나만 쓰이는게 아니라 여러개 가 섞여 쓰이는게 보이기 시작한다 이문제의 경우 일단 그리디 적으로 하기위해서는 내가 들어갈 수 있는 애중에 가장 큰곳에 들어가야 한다 그러면 내가 들어갈 수 있는곳중 큰곳을 어떻게 구할까가 문제인데 이부분을 유니온 파인드로 만들어 줘야한다.
즉 우리는 비행기들의 그룹을 만들어 줘야한다

해당 인풋을 예시로 생각해 보자
현재 게이트는 1번 2번 3번 4번 이있다
4번 비행기는 4번에 들어가는게 가장 알맞다 그 이후는 이후에 들어올 비행기들이 작을 경우에 작은 비행기들이 들어갈 확률이 적기 때문이다

이에 4 이상의 번호인 비행기들이 다음에 들어갈 수 있는 영역인 3번 비행기의 영역과 묶는 다 만약에 이전에 3번 이하 비행기가 들어와있으면 3번 비행기그룹도 이미 만들어 져있을 것이니까 유니온 파인드를 통해 해당 그룹을 묶어준다

#include<iostream>
#include<algorithm>
using namespace std;
int parent[100000];
int arr[100000];
int g, p;
int Find(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = Find(parent[x]);
}

void Union(int x, int y) {
	int parentX = Find(x);
	int parentY = Find(y);
	if (parentX > parentY) {
		swap(parentX, parentY);
	}
	parent[parentY] = parentX;
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> g;
	cin >> p;
	int n;
	int answer = 0;
	for (int i = 0; i < p; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= g; i++) {
		parent[i]=i;
	}

	for (int i = 0; i < p; i++) {
		int f = Find(arr[i]);
		if (f != 0) {
			Union(f - 1, f);
			answer++;
		}
		else {
			break;
		}
	}

	cout << answer;
}

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