급하게임개발

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

이 문제는 플로이드 워셜 알고리즘을 다룬다
다익스트라는 하나의 점에서 부터 다른 vertex까지의 최단 경로를 구하는 것이라면
플로이드 워셜은 전체 점에서의 최단 경로를 구하는 문제이다

다익스트라 알고리즘의 경우 우선순위 큐에 계속 넣어서 경로의 최솟값들을 소모시키면서 다른 vertex들과의 비용을 업데이트 해줬다.

단 플로이드 워셜 알고리즘의 경우 모든 점을 업데이트 해줘야하므로 dp를 통해 순차 탐색을 진행해준다

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}

핵심 로직은 이부분이다 K라는 경유점을 통해서 i to j 의 값과 기존에 i to j의 값을 비교해서 더작으면 넣어주는게 로직이다 .

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int n;
int dp[101][101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dp[i][j] = 0;
			else
				dp[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		dp[from][to] = min(dp[from][to], cost);
	}
	//k는 경유점
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) {
				cout << 0 << ' ';
				continue;
			}
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

이 문제는 dp의 기본적인 문제이다 이문제의 경우 동전의 종류 와 만들 수 있는 동전의 크기가 있다.
이문제는 내가 현재 들고있는 동전을 추가해서 현재의 가치를 만들때 최소한의 동저만 쓴경우만 선택해서 진행한다
한번 표로 봐보자

우리가 가진 동전으로 0원을 만들수 있는 경우의 수는 0 이다 만들수 없다
1원은 현재 1원하나로 만들고 5원 12원으로 만들기 위해서는 -4원 -11원 이 있어야 만들 수 있는데 해당 원수는 없으니 제외한다

자 쭉쭉 진행 되었을 때를 보자

이 상태 에서 10원을 만든다고 가정해보자 9원에서 1원을 추가해서 만드는 방법하나와 5원에서 5원을 하나 추가하는 방법이 있다 이경우 5원에서 동전 하나를 추가해서 만드는게 동전 2개이므로 5원에서 현재 5원을 선택해서 +1 해주는 방식으로 2를 넣어준다 

이문제의 점화식은

arr[i]=min(arr[i], arr[i - coin[j]] + 1);
내가 현재 선택한 동전을 추가했을 때 나올수 있는 경우의 수중 최소를 선택해주면 된다 전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
int n, k;
int coin[100];
int arr[10000] = { 0, };
int main() {
	cin >> n >> k;
	for(int i=0;i<n; i++){
		cin >> coin[i];
	}
	for (int i = 1; i <= k; i++) {
		arr[i] = INF;
		for (int j = 0; j < n; j++) {
			if (i - coin[j] >= 0) {
				arr[i]=min(arr[i], arr[i - coin[j]] + 1);
			}
		}
	}
	if (arr[k]==INF)
		cout << -1;
	else
		cout << arr[k];
}

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

이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.

이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다

해당 로직에 대한 코드는 아래 와 같다

#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
	cin >> h >> w;
	int result = 0;
	for (int i = 0; i < w; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < w - 1; i++) {
		int lmax = 0;
		int rmax = 0;
		for (int j = 0; j < i; j++) {
			if (lmax < arr[j] && arr[j]>arr[i])
				lmax = arr[j];
		}
		for (int j = i + 1; j < w; j++) {
			if (rmax < arr[j] && arr[j]>arr[i])
				rmax = arr[j];
		}
		if (lmax != 0 && rmax != 0)
			result += min(lmax, rmax) - arr[i];
	}
	cout << result;

}

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

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

이 문제는 투포인터 문제이다 또한 에라토스테네스의 체로 소수를  걸러내야한다. 이후  투포인터로 연속된 소수의 합을 구하면 된다 

예시로 우리 15라는 숫자를 연속 된 소수로 만들자고 가정하자
15밑의 소수는

이렇게 존재 한다 우리가 연속 된 소수의 합을 만들기 위해서는 Start부분과 End부분이 있으면 된다

star부터 end까지의 합이 우리가 구하려는 숫자보다 작을 때 end의 index를 1증가 시켜주고 아니면 start의 인덱스를 증가시킨다 구하려는 값과 같으면 해당 구간에서는 이미 구해진 것이므로 start의 인덱스 와 end인덱스를 1증가시켜준다

이런느낌으로 구간을 바꿔가면서 계산 해주면 된다

#include <iostream>
#include <vector>
using namespace std;
vector<int> primeNumbers;
vector<int> check;

//n 이하의 정수에 대한 소수를 에라토스테네스의 체로  걸러냄
void getPrimeNumbers(int n) {
	for (int i = 2; i <= n; i++) {
		if (check[i])
			continue;
		else {
			primeNumbers.push_back(i);
			for (int j = i; j <= n; j += i) {
				check[j] = 1;
			}
		}
	}
}
int main() {
	int n,start,end,cnt;
	cin >> n;
	check.resize(n + 1, 0);
	getPrimeNumbers(n);
	start = primeNumbers[0];
	end = primeNumbers[0];
	int startidx = 0;
	int endidx = 0;
	cnt = 0;
	while (startidx <= endidx && endidx<primeNumbers.size()) {
		int sum = 0;
		for (int i = startidx; i <= endidx; i++) {
			sum += primeNumbers[i];
		}
		if (sum == n) {
			cnt += 1;
			startidx += 1;
			endidx += 1;
		}
		else  if (sum < n) {
			endidx += 1;
		}
		else {
			startidx += 1;
		}	
	}
	cout << cnt;
}

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

이 문제의 경우 다르게보면 조합이지만 이 문제의 분류가 비스마스킹으로 되어 있어서 비스마스킹으로 풀려구 생각했다
이 문제의 비트마스킹은 총 나는 2개를 사용 했는데 일단 team의 점수를 저장하는데 사용 했다 (이 부분에서 좀더  최적화가 가능하나 귀찮아서 진행 하지않았다) 두번째로는 팀들을  나누는데 비트마스킹을 사용했다.

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}

나는 일단 teamP라는 곳에 두명이 차지했을 때의 점수를 넣어줬다 위에처럼 1001일때는 5임으로 4번과 1번팀이 같이 되어있을 때를 나타내며 각팀이 만들어내는 숫자에 따라 점수를 넣어줬다

숫자 일단 이문제의 경우 이렇게 1번팀 0번팀으로 나눌수 있는데 숫자 5의 경우 팀을 위에 그림처럼 나누게 된다

for (int i = 1; i < (1<<n); i++) {
	for (int j = 0; j <= n; j++) {
		if (i & (1 << j))
			team1.push_back(j);
		else
			team2.push_back(j);
	}

이 부분의로직은 이렇게 되는데 i=1부터 시작한다 그  이유는 0번비트만 있을 때는 팀을 만들 수 없으므로 0번 비트  1번 비트 2개가 있는 상황 부터 시작하기 위해서 1번 부터 비트를 사용한다 또한 1<<n 을한 이유는 우리의 테스트 케이스 4를 예시로 들면 비트 4개로 만들수 있는 최댓값은 15인데 1<<4는 16이므로 이부분보다 작을 동안만 우리는 연산을 해주면된다

j변수를 사용하는 루프의 경우는 이제 각비트가 어떤 비트인지 판별하기 위해서 해당 연산을 진행하고 0인지 1인지에 따라 팀에 분배해주게 된다

그후 우리는 두명만이 각 짝을 이뤄 점수가 있으므로

		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}

이런 식으로 각 팀의 연산을 해준다

전체 코드는 아래와 같다

#include <iostream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
int arr[20][20];
vector<int> team1;
vector<int> team2;
int maxresult = 1e9;
int teamP[2097152];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}
	int sum1 = 0;
	int sum2 = 0;
	
	for (int i = 1; i < (1<<n); i++) {
		for (int j = 0; j <= n; j++) {
			if (i & (1 << j))
				team1.push_back(j);
			else
				team2.push_back(j);
		}
		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}
		if (team1.size() && team2.size())
			maxresult = min(maxresult, abs(sum1 - sum2));
		team1.clear();
		team2.clear();
		sum1 = 0;
		sum2=0;
	}

	cout << maxresult;
}

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

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있다 현재 이블로그에 있는 다익스트라 알고리즘에 관한 문제는 비슷한 양상을 보인다

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}

이 부분이 핵심 부분인데

1. 일단 start 즉 시작점으로 부터의 거리를 구할 것이기에 Start -> Start의 toCost를 0 start->start의 다음인덱스 start를 우선순위 큐에 넣는다 (우선순위 큐는 값이 작은게 root 에 있다)

2.그리고 우선순위 큐가 빌때 까지 
현재 우선순위 큐에 들어가 있는 버텍스와 경로들을 뽑아서 해당 경로들에  영향을 받는 다른 vertex들의 cost값을 업데이트 해줘야 한다

3.일단 node1 -> node2 로 갈때의  현재 우선순위 큐에들어가 있는 가장 작은 애를 가져온다 그후 내가 node1을 통해서 가는 node2 까지의 거리와 이전부터 업데이트  해놓은 1부터 node2까지의 거리를 비교해서 작은 값일 때  node2를 통해서 가는 거리들의 값을 업데이트 해준다 그후 다음 업데이트를 할수도 있으니 해당 값들을 우선순위 큐에 넣어주고 반복한다

전체 코드는 아래와 같다

#include <iostream>
#include<queue>
using namespace std;
int n, m;

#define INF 1e9+7
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[5001];
vector<int> distanceV(5001);
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;

		edgeList[temp1].push_back({ temp2,temp3 });
		edgeList[temp2].push_back({ temp1,temp3 });

	}
	int start, end;
	cin >> start >> end;

	distanceV.assign(n + 1, INF);
	djikstraSolution(start);

	cout << distanceV[end];
}

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

솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의  로직을 아는사람이 풀 수 있었다.  핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 1이라는 무게추가 있다고 가정 하자 1이라는 무게추가 있을 때 다음 무게추가 지금 내가 가지고 있는 무게추의 무게보다 크게 되면 사이 무게인 2를 만들 수없다.

다른 예시로 현재 내가 1,1,2 이렇게 총 3개의 무게추를 가지고 있는데 다음 무게추로 6이 들어오게 되면 나는 4를 만들 수  없다

즉 현재 내가 가지고 있는 총 무게추의 무게보다 작은 무게들을 다 만들 수 있을 때 다음에 사용할 무게추는 내가 가지고 있던 총 무게보다 작아야 한다.

해당  로직이 이문제를 풀 수 있게 하는 핵심 로직이었다

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

int N;
int arr[1000];

int main() {

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

    sort(arr, arr + N);

    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }

    cout << res;
}