급하게임개발

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

이 문제의 경우 아마도 프로그래머스 고득점 알고리즘 키트해도 비슷한 문제가 수록 되있을 것이다 단 백준에서는 매우 큰수까지의 비교를 하기 때문에 자료형에 unsinged long long을 해줌으로 범위를 널널 하게 잡아줘야 한다

이 문제의 경우는 각 테이블 마다 특정 시간을 주고 해당 시간 동안 몇명의 인원수를 상대할 수 있는 지를 더해서 친구들의 수와 같으면 정답이게 출력을 해주면 되지만 해당 조건을 만족하는 더 작은 수가 있을  수  있다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	unsigned long long n, m;
	vector <unsigned long long > times;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		unsigned long long tmp1;
		cin >> tmp1;
		times.push_back(tmp1);
	}

	sort(times.begin(), times.end());
	unsigned long long answer = 0;
	unsigned long min = 1;
	unsigned long long max = m * times.back();

	while (min <= max) {
		unsigned long long tmp = 0;
		unsigned long long avg = (min + max) / 2;
		for (unsigned long long i = 0; i < n; i++) {
			tmp += avg / times[i];
		}

		if (tmp < m) {
			min = avg + 1;
		}
		else {
			max = avg - 1;
			answer = avg;
		}
	}
	cout << answer;
}

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