급하게임개발

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

이  문제의경우 LIS 를 사용할 줄 알면 쉬운 문제이다
그후 LIS의 값과 뒤의 인덱스부터의 LIS

#include <iostream>
using namespace std;
int arr[1000] = { 0, };
int n;
int ascendingNum[1001];
int descendingNum[1001];
int maxNum=0;
void getAsc() {
	for (int i = 1; i <= n; i++) {
		ascendingNum[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) {
				ascendingNum[i]=max(ascendingNum[j] + 1,ascendingNum[i]);
			}
		}
	}
}


void getDsc() {
	for (int i = n; i > 0; i--) {
		descendingNum[i] = 1;
		for (int j = n; j > i; j--) {
			if (arr[i] > arr[j]) {
				descendingNum[i] = max(descendingNum[j] + 1, descendingNum[i]);
			}
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	getAsc();
	getDsc();
	for (int i = 1; i <= n; i++) {
		if (ascendingNum[i]+descendingNum[i] > maxNum) {
			maxNum = ascendingNum[i] + descendingNum[i];
		}
	}

	cout << maxNum-1;
}

의 값의 합이 최댓값이 되는 부분을 고른후 -1 해주면 된다 -1을 하는 이유는 해당 방식으로 순열을 고르면 그 범위에서  수가 겹침으로 1개를 빼주는 것이다 41퍼대에서 에러가났는데 그 이유는 dp 배열을 1001로해야하는데 1000으로 해서 틀렸었다

LIS 를 설명 하자면
우리 의 테스트 케이스를 리스트로 넣어보자

이렇게 될것이다 왼쪽 아래에 0을 넣은 이유는 1이전에는 증가하는 수열이 0이기 때문에 넣었다

그리고 1까지 가장 긴  증가하는 순열을 1이다

5일 때는 2이다

자 이제 2일 때를 보자 2일때 가장 증가하는 부분순열은 나 이전에 나보다 작은 애까지의 부분순열의 최댓값을 넣어 주면 된다 즉 나의 이전에 값들중 나보다 작은 값들의 증가하는 부분순열의 최대값들을 더하는 것이다 예시로 더 설명 하도록 하겠다

완성된 그림을 보자 뒤에서 부터 2번째의 5를 보자 얘보다 작은 애들중 가장  큰인덱스는 8번째인덱스의  4이다 해당인덱스의 나를 붙이면 해당 사이즈의 +1이 되기에 5이다

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

이 문제의 경우 DP중에 LCS라는 것에 공부해보았으면 풀 수 있는 문제 였다 처음 보고 나서 부분 순서가 아닌 부분수열로 보아서 틀렸었다 이에 LCS 알고리즘에 대해  공부한 푸니 그리 어렵지 않은 문제였다

#include <iostream>
#include <cstring>
using namespace std;
#define max(a, b) (a > b ? a : b)

int LCS[1002][1002];
char str[1003];
char str2[1003];

int main()
{
	cin >> str >> str2;
	int i, j;
	i = 1;
	while (i <= strlen(str))
	{
		j = 1;
		while (j <= strlen(str2))
		{
			if (str2[j - 1] == str[i - 1])
			{
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			}
			else
			{
				LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
			}
			j++;
		}
		i++;
	}
	printf("%d", LCS[i - 1][j - 1]);
}

맨 처음 

아래 와 같은 표를 만들준다 만들어 주게 되면 7X7 배열이 될텐데 이는 비교하지 않았을 때 에 대한 값 0을 넣어주기 위함이다.

이에 우리가 각 행 마다 채워넣어줄 것은 각각 행까지의 문자들을 열까지의 문자들과 비교했을 때 최대로 나오는 부분 수열의 크기를 넣어줘야한다 이를 바탕으로 다음 수열의 최댓값을 찾을 것이다

즉 C를 열들의 문자와 비교한다 1행 1열이 0인이유는 C를 A까지 비교했을떄 나오는 부분수열이 없기 떄문이다 그후 C를 A C라는 문자열과 비교했을 때 부분수열로 나온것은 C이니 1 지금 집합 C에서의 부분수열이 1밖에 나올수 없으므로 1만채워주게 된다 

그 후 두번째 줄은 C A에서의 부분수열값과 A의 부분수열값을 비교해주게 되는데 C A와 A는 하나의 부분수열 만 공유한다 C A와 A C 도마찬가지이다 C혹은 A만을 공유하기에 1이다 단 이제 C A와 A C A를 비교해주게 되면 현재 C A로 부분수열이 만들어진다 이것은 즉이것은 C만을 비교했을 때 이미 부분수열이 1이었고 그다음 A를 비교했을 때 이부분이 현재 같으므로 이전에  가져왔던 값에 +1을 해주게 된다
그림을 완성 하게 되면 

이런식으로 된다 즉 이  문제를 푸는 핵심은 x축으로의 문자열 과 y축으로 문자열을 비교해서 즉 y 인덱스 까지의 수열에서  행의 문자열들과 몇개가 유사한지를 찾는 것이다 이 부분에서 사용되어야 할게 나의 이전에 문자이다 . 예로 
A C A  와 C A를  비교했다고 가정하자 이미 C를 검사했을 때 x축의 C 의 이후 문자들에서는 무조건 1개의 부분수열이 발생한다는 의미이고  C A와 검사했을 때 C까지 이미 1인 부분수열이 있었으므로 A를 만났을 때  A의 이전까지의 최대 부분수열의 갯수와 지금 일치한 대각선의 값이 +1되게 하여 증가시키는 것이다 즉 A C 와 C를 비교했을 때 이미 1개의 부분수열이 존재함으로 A C A 와 C A 를 비교했을때 +1을 해주게 되는 것이

결국에 이식의 점화식은

LCS[i][j] = LCS[i - 1][j - 1] + 1;

LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);

이렇게 2개가 되는데 
같은 문자를 발견했을 때는 나의 이전 문자까지  비교했을 때의 최대 부분수열의 구성요소 갯수 +1을 해야함으로 i-1과 j-1인덱스의 값에서 +1을 증가시킨다

반대로 틀릴경우에는 즉 y축에서의 나의 이전의 값을 가져오거나 나까지 비교하기전에 최대 부분수열의 인덱스를 가져오게 된다

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

이 문제의 겨우  testcase는 다맞게 나오는데 이상하게 계속 틀렸다고 나왔다. 이에 계속 틀린이유를 찾느라 시간을 많이 소비했다

일단 이문제의 경우 2가지의 경우를 생각해주어야한다

시작점-V1-V2-종점

시작점-V2-V1-종점

여기서 문제에서 시작점에서 V1-V2를 경우하여 종점을 가는것이기에 종점 부터 가는 경우의 수는 생각 해 줄 필요가 없다.

당연히 Vertext와 Edge에 관한 문제이기에 익숙한 다익스트라를 활용했다.

#include <iostream>
#include <queue>
#include <vector>
#include<algorithm>
#define INT_MAX 987654321
using namespace std;
int N, E;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater <pair<int, int>>> djikstra_pq;
vector<pair<int, int>> djikstra_v[801];
vector<int> distanceV(801);
void djikstra(int i) {
	int start = i;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });
	distanceV[start] = 0;
	while (!djikstra_pq.empty()) {
		int toCost = djikstra_pq.top().first;
		int toVertex = djikstra_pq.top().second;
		
		djikstra_pq.pop();
		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < djikstra_v[toVertex].size(); i++) {
			int cost = djikstra_v[toVertex][i].first + toCost;
			int nextIdx = djikstra_v[toVertex][i].second;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ cost,nextIdx });
			}
		}
		
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		djikstra_v[a].push_back({ c,b });
		djikstra_v[b].push_back({ c,a });
	}
	int v1, v2;
	cin >> v1 >> v2;
	int sToV1, sToV2, v1ToV2, v1ToN, v2ToN;
	distanceV.assign(N+1, INT_MAX);
	djikstra(1);
	sToV1 = distanceV[v1];
	sToV2 = distanceV[v2];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v1);
	v1ToV2 = distanceV[v2];
	v1ToN = distanceV[N];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v2);
	v2ToN = distanceV[N];

	int ans = INT_MAX;

	ans = min(ans, sToV1 + v1ToV2 + v2ToN);
	ans = min(ans, sToV2 + v1ToV2 + v1ToN);

	if ((v1ToV2 == INT_MAX)||ans==INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}

내가 이렇게 작성한 코드에서 climits에 INT_MAX를 사용하면 오류가 났다 아마도 테스트케이스중 지나가지 않은 경로에대한 값을 출력할 때 climits에 INT_MAX를 사용하면 값이 오바되면서 최종출력값에 오류가 날것으로 추측했다 이에 Vertex의 최대갯수 800 그리고 가중치의 최대갯수 1000 그리고 구간을 3개로 나누었기에 3을곱한값보다 크지만 INT_MAX보다 작은 값을 최대값으로 지정해주고 풀었다

테스트케이스가 맞을 때 틀렸습니다가 계속 나올 경우 이부분도 생각해서 풀면 좋을거 같다

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

이 문제는 쉽다 일단 다익스트라 알고리즘을 사용하고 간선이 양방향이니 양방향으로 설정해 준다

다익스트라로 각지점의 최단거리를 구해준 후 거리를 정렬하여 범위 안에 있는 아이템에 개수를 더해준 누적값을 구해주면 된다

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
#define INT_MAX 2147483647
using namespace std;
int NumOfItem[101];
vector<pair<int, int>> dijkstraV[101];
vector<int> distanceV(101);

void dijkstra(int start) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; // 비용 노드
	pq.push(make_pair(0, start));
	distanceV[start] = 0;
	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraV[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraV[toVertex][i].second;
			if (cost < distanceV[dijkstraV[toVertex][i].first]) {
				distanceV[dijkstraV[toVertex][i].first] = cost;
				pq.push(make_pair(cost, dijkstraV[toVertex][i].first));
			}
		}
	}
}

int getNumOfItem(int idx, int n, int m) {
	int sum=0;
	for (int i = 1; i <= n; i++) {
		if (distanceV[i] <= m) {
			sum += NumOfItem[i];
		}
	}
	return sum;
}


int main() {
	
	int n, m, r;
	int maxItem=0;
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> NumOfItem[i];
	}

	int from, to, cost;
	for (int i = 0; i < r; i++) {
		cin >> from >> to >> cost;
		dijkstraV[from].push_back({ to, cost });
		dijkstraV[to].push_back({ from,cost });
	}

	for (int i = 1; i <= n; i++) {
		distanceV.assign(101, INT_MAX);
		dijkstra(i);
		if(maxItem < getNumOfItem(i, n, m))
			maxItem = getNumOfItem(i, n, m);
	}
	cout << maxItem;
}

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

이 문제는 다익스트라 알고리즘을 그대로 사용하면 풀 수 있는 문제이다. 자세한 풀이 과정은 이전에 내가 올려놓은

https://fastgamedev.tistory.com/49

이 글의 문제와 똑같이 풀고나서 해당 도착지의 값만 출력해주는 문제라 매우 쉬웠다.

#include<iostream>
#include<queue>
#include<vector>
#define INT_MAX 2147483647
using namespace std;
vector<pair<int, int>> djikstraPQ [1001];
vector <int> distanceV(1001);
void dijkstra(int start) {
	priority_queue < pair<int, int>, vector < pair<int, int>>, greater<pair<int, int>>> pq;// front는 cost second 는 index
	pq.push({ 0, start });
	distanceV[start] = 0;
	
	while (!pq.empty()) {
		int costTo = pq.top().first;
		int toIdx = pq.top().second;
		pq.pop();

		if (distanceV[toIdx] < costTo) {
			continue;
		}

		for (int i = 0; i < (int)djikstraPQ[toIdx].size(); i++) {
			// 나랑 연결되어 있는애가 Second 비용이 front
			int cost = djikstraPQ[toIdx][i].second + costTo;
			if (cost < distanceV[djikstraPQ[toIdx][i].first]) {
				distanceV[djikstraPQ[toIdx][i].first] = cost;
				pq.push({ cost, djikstraPQ[toIdx][i].first });
			}
		}
	}
	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M, start, arrive;
	cin >> N >> M;
	int from, to, cost;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> cost;
		djikstraPQ[from].push_back({ to,cost });
	}
	cin >> start >> arrive;
	distanceV.assign(1001,INT_MAX);
	dijkstra(start);

	cout << distanceV[arrive];
}

이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단  이 문제의 코드는 이렇게 된다

#include <iostream>
#include <queue>
#include <vector>
#define INT_MAX 2147483647
using namespace std;
vector<int> distanceV(20002); //시작점 부터 다른 정점까지의 거리를 저장
vector<bool> visited;
void djikstra(int start, vector<pair<int, int>> dijkstraGraph[]) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 노드 인덱스
	pq.push(make_pair(0, start));
	distanceV[start] = 0;

	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraGraph[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraGraph[toVertex][i].second;
			int nextIndex = dijkstraGraph[toVertex][i].first;
			if (cost < distanceV[nextIndex]) {
				distanceV[nextIndex] = cost;
				pq.push(make_pair(cost, nextIndex));
			}

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge, start;  //vertex는 정점 edge는 간선 start는 시작점을 입력 받는다.
	cin >> vertex >> edge >> start;
	vector<pair<int, int>> dijkstraGraph[20002];//다익스트라 알고리즘의 비용을 저장할 우선순위 큐
	for (int i = 1; i <= edge; i++) {
		int from, to, cost;  //from은 간선사이의 시작점,to는 도착점 , cost는 간선의 비용을 의미
		cin >> from >> to >> cost;
		dijkstraGraph[from].push_back(make_pair(to,cost));
	}
	distanceV.assign(20002, INT_MAX);
	djikstra(start, dijkstraGraph);
	for (int i = 1; i <= vertex; i++) {
		if (distanceV[i] == INT_MAX) {
			cout << "INF"<<endl;
		}
		else {
			cout << distanceV[i] << endl;
		}
	}
}

이 문제의 경우 일단 간선의 방향이 단 방향이다. 일단 이문제의 예시 input에 대한 과정의 그림을 첨부하겠다

이 그림 에서 원으로 되어 있는 그래프는 위에 dijkstra함수에 pq를 그린것이다. 밑에 배열은 distanceV를 그린것이다.

일단 처음 풀이에서

distanceV.assign(20002, INT_MAX);

이 코드를 통해 배열에 큰 값을 다 넣어주었다 이에 처음 벡터에는 INF값만 가득하다 그후 1,0 즉 시작점 1에서 도착지 1로가는 거리는 자기자신이므로 0을 넣어준다 그후 2,2순으로 pq순에서 팝되는 값과 나와 연결되어 있는 다음 인덱스의 값을 더해서 distanceV에 거리를 갱신해 준다. 즉 1이 팝되었을때는 2,3의 거릿값이 갱신된다. 이후 2가팝되었을 때는 3과 4에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.