급하게임개발

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

처음에 이문제는 dp로 접근했다가 시간초과를 맞고 다시 생각해보았다

나는 처음0번부터 k-1번 인덱스 까지의 초밥의 종류를 저장해 놓고 슬라이딩 윈도우에서 해당 인덱스가 나가거나 들어올 때 isEat배열의 요소를 비교해서 인덱스가 빠질때 isEat이 0이될때는 해당 초밥을 안먹는거니 종류에서 빼주고 들어올 때 1이면 이제 먹는 거니 종류에서 +1해줬다

#include <iostream>
#include <vector>
using namespace std;
vector<int> inputData;
int isEat[3001] = { 0, };
int n, d, k, c;
int GetEat() {
	int total=0;
	for (int i = 0; i <= d+1; i++) {
		if (isEat[i] > 0) {
			total += 1;
		}
	}
	return total;
}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> d >> k >> c;
	inputData.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> inputData[i];
	}
	int ans=0;	

	for (int i = 0; i < k; i++) {
		isEat[inputData[i]] += 1;
	}
	isEat[c] += 1;
	ans = GetEat();
	int maxAns = ans;
	for (int i = 1; i < n; i++) {
		isEat[inputData[i - 1]] -= 1;
		if (isEat[inputData[i - 1]] == 0) {
			ans -= 1;
		}
		isEat[inputData[(i + k-1)%n]]+=1;
		if (isEat[inputData[(i + k - 1) % n]] == 1) {
			ans += 1;
		}
		
		maxAns = max(ans, maxAns);
	}
	cout << maxAns;
}

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

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

이 문제의 경우 처음에 투포인터로 분류가 되어있어 풀려고 했는데 투포인터가 불가능 하게 리스트가 4개 있어서 안될거 같다는 생각을 했다 그래서 투포인터를 사용하기 위해서는 어떻게 해야할까라고 생각해봤을 때 a와 b의 합을 c와 d의 합의 모든 경우의 수로 리스트를 만들려고 하였다

즉 c와 d의 합을

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

이런 식으로 만들어 주고

a와 b의 합의 -  를 붙인거가 c와 d를 합친 cmp에 있는 갯수를 더해서 경우의 수를 구하면 된다 근데 갯수를 어떻게 구할지를 생각해보면 -(a+b) 에 대한 거를 algorithm 헤더에 있는 lower_bound와 upper_bound를  이분 탐색으로 해당 수를 찾아 낮은 인덱스 와 높은 인덱스를 찾아 차이가 해당 수의 갯수이니 이를 더해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[4];
vector<int> cmp;
long long ans = 0;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < 4; i++) {
		v[i].resize(n + 1);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> v[j][i];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

	sort(cmp.begin(), cmp.end());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp = v[0][i] + v[1][j];
			int lowIdx = lower_bound(cmp.begin(), cmp.end(), -tmp)- cmp.begin();
			int upIdx = upper_bound(cmp.begin(), cmp.end(), -tmp) - cmp.begin();
			ans += (upIdx - lowIdx);
		}
	}
	cout << ans;
}

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

이 문제는 그냥 크루스칼 알고리즘인데 출력이 불친절하다 그냥 00전에 테스트케이스가 여러개 나오는 문제였다

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

int parent[200000];
int n, m;
vector<pair<int, pair<int, int>>> inputData;

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

bool isSameParent(int x, int y) {
    return findParent(x) == findParent(y);
}

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

int main() {
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break; // 종료 조건

        inputData.clear();
        int tmp1, tmp2, tmp3;
        int cost = 0, totalCost = 0;

        for (int i = 0; i < m; i++) {
            cin >> tmp1 >> tmp2 >> tmp3;
            inputData.push_back({ tmp3, {tmp1, tmp2} });
            totalCost += tmp3;
        }

        // 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        sort(inputData.begin(), inputData.end()); // 간선 정렬

        for (int i = 0; i < inputData.size(); i++) {
            if (!isSameParent(inputData[i].second.first, inputData[i].second.second)) {
                uni(inputData[i].second.first, inputData[i].second.second);
                cost += inputData[i].first;
            }
        }

        cout << totalCost - cost << "\n";
    }

    return 0;
}

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

이 문제는 RGB거리 문제의 발전형이다 기존에는 사이클을 검사안했으나 이번에는 사이클을 검사해야한다 그래서 이문제를 풀기위한 핵심은
첫번째 집의 색깔을 정해주고 나머지 집들의 dp를 돌리는 것이다

어떻게 정하면 되는지는 우리는 원래 dp 를 풀때 각라인의 최솟값을 넣는데 이 최솟값을 만들 때 우리는 나머지 선택을 하지못하게 하면된다

해당 예제를 예시로 보자

평소에 우리가 dp를 구할  때 우리는 26 40 83을 min 때리고 이를 바탕으로 다음라인에서 비교 해준다 평소대로 하게된다면 우리는 다음  dp 행을 구할 때 최소 색깔을 선택함으로 우리가 색을 정할 수가 없다 만약에 우리가 999999 40 999999 이런식으로 dp 행을 놓게 된다면 무조건적으로 40이 선택된다 이러한 로직을 바탕으로

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

해당 로직이 작성된다 first는 첫번째 집이 고른 색이다 첫번째 집이 빨간색을 골랐을 때 우리는 파란색 초록색을 고르는 선택지를 없애버리기 위해서 dp행이 첫번째의 고를 선택지 에서 지워버리는 것이다



이로직 뺴고는 dp 점화식 자체는 별반 다른지 않다

내가 빨간색을 선택했을 때 이전에 초록색 혹은 파란색을 선택했을 때 의 값중 최솟 값을 선택하면된다 

즉 점화식 자체는

	for (int i = 1; i < n; i++) {
		dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
	}

이렇게 된다

전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][3];
int dp[1001][3];
int maxVal = 987654321;
int answer = 987654321;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

		for (int i = 1; i < n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		for (int i = 0; i < 3; i++) {
			if (first == i)
				continue;
			answer = min(answer, dp[n-1][i]);
		}
	}

	cout << answer;
}