급하게임개발

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에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.

이 문제는 dp문제이다

#include <iostream>
#include <algorithm>
using namespace std;
//dp[i][j]= 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j였을 떄 배낭에 들어간 물건의 가치합의 최댓값
//예를 들어
int dp[101][100001];
int W[101];
int V[101];
int main() {
	//N은 물건의 갯수를 의마한다.
	//K는 버틸수 있는 물건의 무게를 의미한다.
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (j - W[i] >= 0) {
				//현재 무게의 최댓갑은 이전아이템까지 넣은 단계에서의 최댓값과
				//지금 아이템의 무게를 넣은 물건의 값을 비교하여 더 큰값을 넣는다.
				//i번째 물건을 넣을 지 말지가 중요하다.
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]+V[i]);
			}
			else {
				//현재 아이템을 넣었을때 무게가 오바된다면 넣지 않고 이전걸 그대로 가져온다
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][K];
}

코드를 살펴보면 일다 우리는 가지고 있는 첫번째 아이템 부터 차근차근 가방에 넣을 것이다. 차근차근 넣을 때 제한 무게를 초과한다면 그 아이템은 넣지 않는다가 이문제의 핵심이다. 즉 i번째 아이템을 넣은 것과 안 넣은 것의 최댓값을 계속 갱신해주면서 진행하는게 해당 문제의 해결 방법이다. i=1일때 우리는 가방에 이 아이템을 넣을지 말지 결정 한다. dp[0][0]은 어차피 0이다 하지만 무게해당하는 j값이 0이기에 일단 넣지 않는다. 이에 dp[1][6]=13이다 즉 1번아이템을 넣었을 때의 무게는 6이고 13이다라는 의미이다 이제 2번아이템을 넣는다고 가정해보자 2번아이템도 마찬가지로 진행이된다. dp[4][4]의 가치는 일단 8이다 하지만 이제 dp[6]으로 간다면 2번까지 넣어서 6이하의 무게를 만든 가방보다 1번만 넣어서 6이하의 무게를 가진 가방의 가치가 더높으므로 dp[2][6]=13이다. 

자이제 3번아이템까지 넣는다고 가정하자  일단 dp[3][3]=6이다 dp[2][4]=8이고 이에 따라 dp[3][4]=8이다

dp[3][7]의 기준으로 보자 지금 까지는 dp[1][6]의 값이 계속 들어 와서 13이었을 것이다. 하지만 3번 아이템을 넣는다고 가정해보았을 때 dp[2][4]+dp[3][3] 즉 dp[2][4]+V[i]의 값이 기존의 dp[2][7]즉 dp[1][6]의 값이 계속 넣어진 상황 보다 큼으로

갱신된다 

이 문제는 너무 쉽다 dp이긴 한데 점화식으로 풀었다고 하기엔 애매하다 1부터 123을 다 더해서 작으면 다시 더한후 그값이 커지면 그 이후로는 계산을 안하면 되겠다는 생각으로 이 문제를 풀었다 이문제는 생각 보다 매우 쉬웠다 설명할것도 없이 코드를 보면 이해가 될것이다

#include <iostream>
#include<queue>
using namespace std;
int T;
queue <int> n;
int answer[12];
int solution(int start,int answerindex) {
	if (start == answerindex) {
		answer[answerindex]++;
	}
	else if (start > answerindex) {
		return 0;
	}
	else {
		solution(start + 1, answerindex);
		solution(start + 2, answerindex);
		solution(start + 3, answerindex);
	}
	return 0;
}
int main() {
	cin >> T;
	int temp;
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int i = 1; i <= T; i++) {
		cin >> temp;
		n.push(temp);
	}
	while (!n.empty()) {
		temp = n.front();
		n.pop();
		solution(0, temp);
		cout << answer[temp] << endl;
	}
}

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

DP는 해도해도 실력이 확실히 점화식을 잘세워야 하는 것 같다 이문제의 경우 점화식이 무조건 필요했는데 사실 문제 이해가 잘 안 갔어서 푸는데 4시간 걸렸다......알고리즘 빨리 풀어야하는데  이문제의 경우는 일단 예시로 나온

을 기준으로 하면 동전의 갯수 만큼의 경우의 수를 생각 해주어야 했다

맨처음 첫번째 동전인 1원만으로 1원 부터 10원 까지 만들 수 있는 경우의 수를 dp 에 채워 준다 그 후

2원 부분의 행을 채워 줘야한다 2원 부분의 행은 무조건 해당 단계에서 2원만을 사용해서 그 해당 수를 만들어 주는 경우의 수다 이부분에서는 5원에 대한 생각은 해주지 않습니다 2원의 행은 2원과 1원 부분만을 이용해서 그 해당 원수를 만드는 것 입니다

이에 이렇게 쭉 구하면서 5원 부분까지 가면 10월을 만들 때 딱 5원을 추가하여 10원을 만드는 경우의 수는 5원으로 5원을 만든 경우의수와 1원과 2원으로 만든 5원의 경우의 수와 1원으로만 만든 5원의 경우의 수를 더하여 4가지가 나온다 이렇게 생각을 하게 되면 이문제의 dp를 추정 할 수 있습니다 하지만 위에거를 그대로 사용하여 2차원 배열을 사용하게 되면 4mb를 초과하는 사태가 발생하여 틀렸습니다가 생겼습니다 이에 우리는 위에 식을 이용해 점화식을 더간단한 점화식을 만들어야합니다.

점화식을 세울때 우리가 봐야할 부분은 합계입니다  2원에서의 합계를 보시지요 자 기존에 1원에서 만 만들었던 값에서 자기자신을 뺀 부분에서의 값을 더해줌으로서 지금 원을 만드는데 2원을 넣었다고 가정했을 때의 경우의 수를 더해주게 됩니다.

각 2원의 행을 예시로 봅시다 2원의 행은 지금 계속 표를 보면 0원에서 2원

dp[2] += dp [0]   2

dp[3] += dp [1]   2

dp[4] += dp [2]   3

즉 dp[2] 의경우 1원으로 만든 경우의 수 + 0원의 경우의 수가 됩니다 이유는 0원에서 2원을 고름으로서 2원을 만들 것이기 때문입니다 이에

dp 배열의 합계 부분들은 이런식으로 값이 바뀌게 됩니다.

즉 먼저 하나의 코인으로 해당 값을 만든 다고 가정하고 그 경우의 수에서 나의 동전값을 뺏을 때의 경우의 수를 더해줘야 합니다 

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

이 문제는 내가 지금 까지 DP배열을 1차원 배열로 만드는데 익숙 해져서 그런지 2차원 배열로 설정 하는 것을 생각을 못해서 어려운 문제 였다. 이 문제의 경우 나는 이렇게 생각 해주었다.

일단 나는 이문제를 1번 아이템 부터 4번아이템을 넣어준다고 가졍하였다 이문제에서 0은 어떠한 아이템도 안 넣었다고 생각해서 0이자 무게가 0이라고 생각을 했다 이렇게 생각하지 않으면 너무 헷갈렸다 그래서 1번을 넣었을 때 무게가 6이고 7인 경우에는 1을 넣었기 때문에 1의 무게인 13을 넣었다. 1을 넣었을 때 무게가 1,2,3,4 일 수는 없으니 1을 넣지 않았다는 표시이자 안 넣었고 무게도 0이니 0으로 한다. 2번아이템을 넣었을 때 도 마찬가지 무게가 1,2,일 때는 2번을 넣었을 때

무게가 4로 초과되니 0으로 표시한다 그후 무게가 4랑 5일때는 

나의 이전 단계인 1을 넣었을 때의 무게들 중 나를 안넣었다고 가정한 무게 + 나의 무게를 했을 때와 이전단계의 무게들과 비교하여 더큰 값을 넣어준다. 이것을  dp로 표현 하면

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); 

예시로 dp[2][6]은 dp[1][2]+v[2] 과 dp[1][6]일 때를 비교한다 이 의미는 1을 먼저 넣을 안넣을 지 결정하는 상태에서 무게가 2일때+나의 더했을 때의 가치와 1을 넣을 안넣을지 결정했을 무게가 6인 경우를 비교하여 더 큰 값을 선택한다.

쉽게 설명하자면

1을 넣을지 말지 결정했을 때  특정 무게를 맞춘다고 가정했을 때 나의 무게를 더해서 그 무게를 맞춘다고 가정한 값과 이전 단계에서 그 무게를 달성했을 때의 값을 비교하여 큰값을 선택해 주는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[101][100001];//가방 물건의 번호,내가방의 무게
int W[101];
int V[101];
int main() {
	int maxItemNum;
	int maxItemWeight;
	cin >> maxItemNum >> maxItemWeight;

	for(int i=1; i<=maxItemNum; i++){
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= maxItemNum; i++) {
		for (int j = 1; j <= maxItemWeight; j++) {
			if (j - W[i]>=0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[maxItemNum][maxItemWeight];
}

그래서 이러한 점화식으로 이문제를 풀면 전체 식이 이렇게 된다. 1차원으로 dp를 세우는 거 뿐만 아니라 다차원의dp 도 세우는 방법을 연습해야 할거 같다.