급하게임개발

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

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

이 문제는 투 포인터 문제이다 이중 포문으로도 구현이 가능하나 해당 방식으로 할경우 시간 복잡도가 커진다 이에 루프문 한개로 해당 문제를 해결하는 게 핵심이다

이 문제의 로직은 일단 이어지는 선들을 최대한 길게 이어진  후 끊어졌을 때 부터 선을 다시 쭉 길게 이어서 이 선 2개의 길이의 합을 구하는 것이다

주어진 테스트 케이스를 v1.first를 기준으로 정렬하면 해당 그림 처럼 된다. 아래칸은 시작점 위에 칸은 끝나는 점을 의미한다. 이 리스트는 오름차순 정렬을 했다고 가정했기에 첫번째로 나오는 선은 1부터 시작해서 길게 늘일 것이다 즉 첫번째 상태일때

이렇게 된다 그후에 2부터 5까지를 비교했을 때 이 두선은 이어짐으로 start는 그대로 두고 end를 5로 바꿔준다 

그 다음 3부터 5까지도 이 선과 끝점은 같지만 시작점이 다름으로 기존에 있던 선임으로 포함을 시키지 않는다 아직도 start는 1 end 는 5이다
그 후 6과 7을 만났을때는 아래그림처럼 된다

6과 7을 만났을 때는 새  선임으로 기존에 있던 선의 길이를 일단 값을 누적시켜준후 리스틀 끝나지 탐색한후 해당 start와 end값을 다시 더해준다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	int sum = 0;
	cin >> n;

	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int n1, n2;
		cin >> n1>>n2;
		v.push_back({ n1,n2 });
	}
	sort(v.begin(), v.end());
	int start = v[0].first;
	int end = v[0].second;
	for (int i = 1; i < n; i++) {
	

		if (end > v[i].first) {
			end = max(v[i].second, end);
		}
		else {
			sum += end - start;
			start = v[i].first;
			end = v[i].second;
		}

	
	}
	sum += end - start;
	cout << sum;
}

이 문제의 경우 내가 본 코테에서 나온 문제를 임의로 각색한 문제이다. 충분히 풀 수 있는 문제였으나 배가 고파서 못풀었지만 생각하니까 매우 쉬운 문제였다.. 이래서 아침밥이 중요한가 보다.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int arr[1001][1001];
bool visited[1001][1001];
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 hp=100;
	int maxhp = 100;
	int startX, startY;
	stack<pair<int, int>> bfss;
	cin >> startX >> startY;
	bfss.push(make_pair(startX, startY));

	while (!bfss.empty()) {
		startX = bfss.top().first;
		startY = bfss.top().second;
		visited[startX][startY] = true;
		if (arr[startX][startY] == 1) {

		}
		else if (arr[startX][startY == 2]) {
			hp -= 20;
			if (hp <= 0) {
				break;
			}

		}
		else if (arr[startX][startY] == 3) {
			hp += 30;
			arr[startX][startY] = 1;
		}

		if (startX + 1 < N && !visited[startX + 1][startY]&&arr[startX+1][startY]!=0) {
			bfss.push(make_pair(startX + 1, startY));
		}
		else if (startX - 1 >= 0 && !visited[startX - 1][startY]&& arr[startX - 1][startY]!=0) {
			bfss.push(make_pair(startX - 1, startY));
		}
		else if (startY - 1 >= 0 && !visited[startX][startY - 1]&& arr[startX][startY - 1]!=0) {
			bfss.push(make_pair(startX, startY - 1));
		}
		else if (startY + 1 < N && !visited[startX][startY + 1]&& arr[startX][startY + 1]!=0) {
			bfss.push(make_pair(startX, startY + 1));
		}
		else {
			bfss.pop();
		}
	}
	cout << hp;
}

문제: 플레이어는 N x N 던전 안에 있다 이때 플레이어는 자신이 갈 수 있는 모든 곳을 탐험 해야 한다. 이 던전에는 몬스터방 물약방 일반방이 있으며 몬스터방에 들어갔을 시 몬스터는 잡지 못하고 플레이어의 피가 20 감소한다 물약방에 들어가면 그 방은 일반 방으로 바뀌고 플레이어의 피가 30이 증가한다. 플레이어가 던전을 모두 돌고 나서의 플레이어의 HP를 출력하라. 플레이어의 HP가 0일시 즉시 탐험을 종료하고 0을 출력한다.

출력 예시:

3
1 3 1
0 2 0
0 2 0
0 0

정답:40