급하게임개발

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

이 문제의 경우 문제 분류에 부르트 포스 라고 되어있지만 정확히는 dfs 백트래킹이라고 보는게 맞을거 같다 
처음에는 0 부터 9876543210 까지 수들을 검사해서 해당 수가 감소하는 수 인지를 검사하는 방법을 사용했지만 해당 방법은 시간초과를 유발했기에 dfs와 백트래킹을 사용하여 해당 문제를 풀었다

해당 이미지를 보자 우리가 백트래킹으로감소하는 수를 만들려고 할시 반복문의 범위를 단지 이전 자리의 숫자의 값까지만 증가시켜주면서 넣어주면 된다

#include <iostream>
using namespace std;
long  long arr[1000001];
long  long n;
long  long numCnt;
long  long idxOfNum = 10;
void makeDecreaseNum(long  long num , long  long numOfone , long  long cntOfNum) {
	if (cntOfNum==numCnt) {
		arr[idxOfNum] = num;
		idxOfNum++;
	}
	else {
		num = num * 10;
		for (long  long i = 0; i < numOfone; i++) {
			makeDecreaseNum(num + i, i, cntOfNum+1);
		
		}
	}

}
int main() {
	cin >> n;
	for (long  long i = 0; i < 1000001; i++) {
		arr[i] = -1;
	}
	for (long  long i = 0; i < 10; i++) {
		arr[i] = i;
	}
	for (long  long i = 2; i <= 11; i++) {
		numCnt = i;
		for (long  long j = 1; j <= 9; j++) {
			makeDecreaseNum(j, j, 1);
		}
	}
	cout << arr[n];
}

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

이 문제의 경우 dfs로 풀이를 진행했다  이 문제를 풀 때 한가지 잘못 생각한점으 치즈 안의 공간은 실내온도에 접촉 한것이아니라는 것이었다.  문제에서 테두리에는 치즈가 없다고 명시해주었으므로 dfs혹은 bfs로 0,0 위치 와 연결된 공간들을 모두 -1  로 체크 해주었다 그후 dfs를 한번더 진행하여 치즈들중 외부공기 2층이랑 이어진 공간들에 대해서 다른 배열에 넣어서 계산해주고 다시 0,0부터 dfs를 돌려 외부공기를 체크해 주었다.

#include <iostream>
using namespace std;
int N, M;
int arr[100][100];
int willMelt[100][100];
int xIdx[4] = { 1,0,-1,0 };
int yIdx[4] = { 0,1,0,-1 };
bool isVisited[100][100] = { 0, };
bool canGo(int x, int y) {
	if (x < N && y < M && x >= 0 && y >= 0) {
		if (!isVisited[x][y] && (arr[x][y] == 1))
			return true;
		else
			return false;
	}
	else
		return false;
}
void copyArr(int arr[100][100], int arr2[100][100]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			arr[i][j] = arr2[i][j];
		}
}
void dfs(int x, int y) {
	int zeroCount = 0;
	for (int i = 0; i < 4; i++) {
		if (arr[x + xIdx[i]][y + yIdx[i]] == -1) {
			zeroCount += 1;
		}
		if (canGo(x + xIdx[i], y + yIdx[i])) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			dfs(x + xIdx[i], y + yIdx[i]);
		}
	}
	if (zeroCount >= 2) {
		willMelt[x][y] = 0;
	}

}
void airDfs(int x, int y) {
	arr[x][y] = -1;
	for (int i = 0; i < 4; i++) {
		if (x + xIdx[i] < N && y + yIdx[i] < M && x + xIdx[i] >= 0 && y + yIdx[i] >= 0 && !isVisited[x + xIdx[i]][y + yIdx[i]]&& (arr[x + xIdx[i]][y + yIdx[i]] == 0|| arr[x + xIdx[i]][y + yIdx[i]] == -1)) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			arr[x + xIdx[i]][y + yIdx[i]] = -1;
			airDfs(x + xIdx[i], y + yIdx[i]);
		}
	}


}
void meltCheese() {
	copyArr(willMelt, arr);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!canGo(i, j))
				continue;
			isVisited[i][j] = true;
			dfs(i, j);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	copyArr(arr, willMelt);
}
bool isMelted() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] != -1)
				sum += 1;
		}
	}
	if (sum == 0)
		return true;
	else
		return false;
}
void process() {
	int year = 0;
	airDfs(0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	while (!isMelted()) {
		meltCheese();
		airDfs(0, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				isVisited[i][j] = false;
			}
		}
		year += 1;
	}
	cout << year;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}
	process();
}

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

이 문제의 경우 전형 적인 다익스트라 알고리즘으로 풀 수 있을거 같았다 그 이유는 첫시작 점이 0 그리고 endPoint인 n-1 까지 가는 것으로 정해졌기에

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

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}

굳이 플로이드  와샬로 전체 의 거리는 구할 필요가 없기 때문이다 

항상 다익스트라에서 쓰는 로직과 비슷하다 일단 StartVertex를 StarVertex까지의 거리가 0이라 두고 큐에다가 넣는다

그후 edgeList에서  startNode와 연결된 모든 노드들과 계산하여 거리를 구한후 priority queue에 넣는다 이를 반복하면 결국에 마지막 노드까지 가는거리가 최단거리로 완성이 된다.

이문제의 경우 단 djikstra를 풀때 조건이 하나가 추가되는데 해당 vertex의 시야값이 1이면 가지 않는 것이다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1234987654321
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> djikstra_pq;
vector<pair<int, long long>> edgeList[300000];
vector<long long> distanceV(300000);
bool canGo[300000] = { 0, };
int n, m;
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> canGo[i];
		canGo[i] = !canGo[i];
	}

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		edgeList[from].push_back({ cost,to });
		edgeList[to].push_back({ cost,from });
	}
	distanceV.assign(n , INF);
	djikstraSolution(0);
	if (distanceV[n - 1] >= INF)
		cout << -1;
	else
		cout << distanceV[n-1];
}

전체 코드는 위와 같다

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

이 문제의 경우 전형적인 플로이드 워셜 알고리즘을 사용 하여 구현한다
핵심이 되는  부분은

void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

k즉 i to k , k to j 즉 어떠한 정점 까지 갈때 중간에  거치는 지점이다 즉 계속 거치는 지점을 업데이트 해주면서 최소 거리를 구하는게 플로이드 워셜의 로직이다

#include <iostream>
#define INF 987654321
using namespace std;
int dp[401][401];

int v, e;
void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	int maxValue = INF;
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dp[i][j] == 0;
			else
				dp[i][j] = INF;
			
		}
	}
	for (int i = 0; i < e; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		dp[from][to] = value;
	}

	floyd();

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (dp[i][j] + dp[j][i] < maxValue && !(i==j)) {
				maxValue = dp[i][j] + dp[j][i];
			}
		}
	}
	if (maxValue >= INF) {
		cout << -1;
	}
	else {
		cout << maxValue;
	}
}

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

이 문제의 경우 점화식을 세우기 빡셌다 이문제의 경우 일단 대충의 로직은

이 상태에서 시작하게 된다 맨위에 파란부분은 수고 그이후의 행들은 해당 숫자를 만드는 데 사용하는 수의 개수를 의미합니다 현재 1행에 숫자 1들이 들어간 이유는 각 수를 만드는데는 자기자신 하나만 필요하기 때문입니다.

자 그리고 다음 행을 봅시다
0을 만드는데는 어차피 0 하나로 밖에 못만드니 

이렇게 채워 줍시다
그다음 2행을 채우게 되면 숫자 2개로 해당 수를 만드는 방법을 봅시다 1은 1+0 과 0+1 로만들 수 있습니다 2는 1+1과 0+2와  2+0으로 만들 수있습니다 우리는 여기서 알수있는게 해당행의 이전행에서의 나자신까지의 합을 모두 더해주면 된다는 것을 알수 있습니다. 0을 선택하게 되면 자동을 2가선택 1을 선택하면 자동으로 1이선택 2를 선택하면 자동으로 0이선택되니 이전행의 자신 열까지의 합을 넣어주면 됩니다

그후 3행은 숫자 3개를 이용하는 것이기에 이전 행에서 2개를 선택한 로직에서 추가로 확장하면 됩니다 숫자 3개로 1을 만드는 방법은 (0+0)+1 , (1+0)+0,  (0+1)+0 이고 2의경우는 이전에 2개를 선택한거에 추가로 해당 수를 제외한 수를 더해주면 자동으로 더해지게 됨으로 이전행의 열들의 값을 더해주면 됩니다

결과적으로 그림이 이렇게 되서 완료가 됩니다.
해당 코드를 구현하면

#include <iostream>
using namespace std;
long long m = 1000000000;
long long dp[204][204];
int main() {
	long long n, k;
	cin >> n >> k;

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


	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[k][n];
}

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

이 문제는 LIS 문제이다  그 이유는 이 문제의 경우 학생들을 원하는 위치이 넣을 수 있으므로 정렬되어 있지 않은 학생들을 정렬된 학생의 알맞은 위치에 넣으면 되는것이다 즉 전체 수에서 LIS만큼  뺴주면 되는 문제였다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200];
int dp[200] = { 0, };
int lis = 0;
int main() {
	int n,x,y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <i; j++) {
			if (arr[i] > arr[j]) {
				dp[i]=max(dp[i], dp[j] + 1);
				lis = max(lis, dp[i]);
			}
		}
	}
	cout << n-lis;
}

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

이 문제는 그리디 문제이다 처음에 이문제를 완전 탐색으로 하려 했으나 완전 탐색을 하라고 낸 문제는 아닌거 같았다 이에 s->t 를 하기보다는 t->s 를 해야겠다고 생각했다 이에 끝문자가 A면 단순 Pop을 B면 Pop을 하고 뒤집어주었다

#include <iostream>
#include<string>        
#include<algorithm>
using namespace std;
int main() {
	string s, t;
	cin >> s;
	cin >> t;
	while (1) {
		if (s.size() == t.size()) {
			if (t == s) {
				cout << 1;
			}
			else {
				cout << 0;
			}
			break;
		}
		if (t[t.size() - 1] == 'A') {
			t.pop_back();
		}
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}
}

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

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

int dfs(int x,int y) {
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다