급하게임개발

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

이 문제는전형 적인 dp문제이다 점화식만 세우면 문제되는 부분은 없었다 점화식은 dfs랑 비슷하게 생각하면되지만 
이문제의 핵심은 현재 칸에 왔을 때 내가 갈 수 있는 칸이 더많은 칸으로 가는거를 골라야한다 .

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int arr[501][501] = { 0, };
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> inputData;
int n;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dp[501][501];
bool canGo(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		return true;
	}
	return false;
}
int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			inputData.push({ arr[i][j],{i,j} });
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = 1;
		}
	}
	while (!inputData.empty()) {
		int curCost = inputData.top().first;
		int curX = inputData.top().second.first;
		int curY = inputData.top().second.second;
		inputData.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];
			
			if (canGo(nextX, nextY) && curCost < arr[nextX][nextY]) {
				dp[curX][curY] = max(dp[nextX][nextY] + 1, dp[curX][curY]);
			}
		}
	}

	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}

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

이 문제는 dp 와 비트마스킹을 섞은 문제이다 일단 이문제는 이전
https://www.acmicpc.net/problem/10844

10844번 문제를 풀었을 경우 쉬웠을 것이다

일단 우리는 작은 단계에서 부터 검증을 하자 일단 자릿수가 2일때의 계단수를 구해보자

길이 가 3일때는 어떻게 될까 우리는 이전 길이가 2인계단수에서 답을 구할수 있다
자리가 3이고 첫시작수가 2일때 우리는 이전 1과 3에서 값을 가져와서 할수있다 이에

            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }

이렇게 된다 k는 현재 어떤수가 사용되었는지를 비트마스킹으로 나타낸것이다 우리는 이후에 모두 사용된 1023일때만의 값을 구해서 답을 구할 것이다

#include <iostream>
using namespace std;

const int mod = 1e9;
int dp[100][10][1024]; // (자리수, 마지막 숫자, 방문한 숫자 상태)

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

    // 초기 상태 설정
    for (int j = 1; j <= 9; j++) {
        dp[0][j][1 << j] = 1;  // 첫 번째 자리는 1~9만 가능 (0은 불가능)
    }

    // DP 점화식 수행
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }
        }
    }

    // 정답 계산 (n번째 자릿수에서 0~9까지 모든 숫자를 포함하는 경우)
    int answer = 0;
    for (int j = 0; j <= 9; j++) {
        answer = (answer + dp[n - 1][j][1023]) % mod;
    }

    cout << answer << endl;
    return 0;
}

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

이 문제는 bfs에 이분탐색을 통한 적절한 값 찾기 이다 
처음에는 갈수있는 경로별 최댓값을 구하려 했으나 시간초과가 났다 당연한 얘기다

자 일단 이코드는 bfs를 통해 특정 노드에서 노드로 가는 경우의 수를 모두 탐색하는데 이때 우리는 무게를 계속 정해주고 해당 무게가 특정 다리의 cost를 넘어가면 이후 탐색의 값을 좀더 줄여 나가는 방식으로 진행한다 도착점에 도착하면 그이후로 탐색하지않는다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector < pair < int , int >> v[100001];
bool isVisited[100001];
int maxNum = 1000000000;
int bfs(int from, int to) {
	int lo = 1;
	int hi = maxNum;
	int mid;
	int ans;
	while (lo <= hi) {
		mid = (lo + hi) / 2;

		for (int i = 0; i < n+1; i++) {
			isVisited[i] = false;
		}

		queue<int> q;

		q.push(from);
		isVisited[from] = true;
		bool canMore = false;

		while (!q.empty()) {
			int node = q.front();
			q.pop();

			if (node == to) {
				canMore = true;
				break;
			}

			for (int i = 0; i < v[node].size(); i++) {
				int next = v[node][i].first;
				int cost = v[node][i].second;
				if (isVisited[next])
					continue;
				if (mid > cost)
					continue;
				isVisited[next] = true;
				q.push(next);
			}
		}

		if (canMore) {
			lo = mid + 1;
			ans = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return ans;

}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	int from, to;
	cin >> from >> to;
	int ans = bfs(from, to);
	cout << ans;

}

이 문제는 유니온 파인드 문제이다 이전 게시글에 크루스칼 알고리즘을 사용하면 쉽게 풀린다

#include <iostream>
#include <queue>
using namespace  std;
int n;
int parent[1000];
priority_queue < pair<long long , pair<int, int >> , vector < pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>> > inputData;

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = findParent(parent[x]);
}

void uni(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);
	parent[parentY] = parentX;
}

bool isSameParent(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);
	if (parentX == parentY)
		return true;
	else
		return false;
}

int main() {
	cin >> n;
	int tmp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmp;
			if (i == j)
				continue;
			inputData.push({ tmp,{i,j} });
		}
	}
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	long long ans = 0;
	while (!inputData.empty()) {
		int from = inputData.top().second.first;
		int to = inputData.top().second.second;
		int cost = inputData.top().first;
		inputData.pop();
		if (!isSameParent(from, to)) {
			uni(to, from);
			ans += cost;
		}
	}
	cout << ans;
}

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

이 문제는 일단 누적합을 이용해서 구간들의 합을 구해야 하는데 구간합간의 단순 비교를 하면 시간 초과가 뜨기 때문에 이문제의 경우 일단 한 배열의  구간 합들을 따로 저장 해놓고  이를 정렬한 후 이분탐색으로 그값의 하위 인덱스와 상위인덱스의 차를 더해주면 된다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> valOfA;
vector<int> valOfB;
vector<int> cmpB;
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	iostream::sync_with_stdio(false);
	int t;
	int n, m;
	cin >> t;
	cin >> n;
	valOfA.resize(n + 1,0);
	int tmp;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		valOfA[i] = tmp + valOfA[i - 1];
	}
	cin >> m;
	valOfB.resize(m + 1, 0);
	for (int i = 1; i <= m; i++) {
		cin >> tmp;
		valOfB[i] = tmp+ valOfB[i - 1];
	}

	for (int i = 0; i <= m; i++) {
		for (int j = i+1 ; j <= m; j++) {
			cmpB.push_back(valOfB[j] - valOfB[i]);
		}
	}
	sort(cmpB.begin(), cmpB.end());
	int start = 1;
	int subAarr = 0;
	long long ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			subAarr =valOfA[j] - valOfA[i];
			subAarr = -(subAarr)+t;
			int lowIdx = lower_bound(cmpB.begin(), cmpB.end(),subAarr) - cmpB.begin();
			int upIdx = upper_bound(cmpB.begin(), cmpB.end(), subAarr) - cmpB.begin();
			ans += upIdx - lowIdx;
		}
	}
	cout << ans;

}

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

이 문제는 위상 정렬 입니다
근데 일반 위상정렬 하고 다르게 cost 값을 갱신 해주어야 했습니다 어찌 보면 플로이드 워셜하고 비슷 하다고 볼수 있습니다
일단 점입 차수가 0인것부터 큐에 넣고 next들을 갱신해 줍니다 next들은 이전애들이 다 되어야하기 때문에 플로이드 워셜처럼 최단이 아닌 최장을 저장하고 있어야 했습니다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int t;
int main() {
	cin >> t;
	int n, k;
	for (int i = 0; i < t; i++) {
		cin >> n >> k;
		vector<vector<int>> inputData(n+1);
		vector<int> cost;
		vector<int> resultCost;
		int inCount[1001] = { 0, };
		int tmp1, tmp2;
		cost.resize(n + 1);
		resultCost.resize(n + 1);

		for (int i = 1; i<= n; i++) {
			cin >> cost[i];
			resultCost[i]=cost[i];
		}
		for (int i = 0; i < k; i++) {
			cin >> tmp1 >> tmp2;
			inputData[tmp1].push_back(tmp2);
			inCount[tmp2]++;
		}

		queue<int> q;
		for (int i = 1; i <= n; i++) {
			if (inCount[i] == 0) {
				q.push(i);
			}
		}
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int i = 0; i < inputData[cur].size(); i++) {
				int next = inputData[cur][i];
				inCount[next]--;
				if (resultCost[cur] + cost[next] > resultCost[next]) {
					resultCost[next] = resultCost[cur] + cost[next];
				}
				if (!inCount[next]) {
					q.push(next);
				}
			}
		}
		int w;
		cin >> w;
		cout << resultCost[w] << endl;
	}
}

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