굳건하게

문제 : https://www.acmicpc.net/problem/2463

[ 알고리즘풀이 ]

문제 예시를 통해 자세히 뜯어보겠습니다.

다음과 같은 상황에서 u < v 인 모든 두 정점 u, v 에 대한 Cost(u, v) 의 총합은 다음과 같습니다.

→ 간선을 제거했을 때, 경로가 끊기는지가 중요!

 하지만, 이렇게 답을 구하려면 M개의 간선을 하나씩 제거하며, 매번 Union-Find 기법으로 N개의 정점에 대해서 Grouping 을 해줘야되므로 O(N * M) 복잡도를 가진다. 따라서, 제한 시간 안에 문제를 해결할 수 없다.

 시간 제한 안에 문제를 해결하려면 관점을 전환해야됩니다. Cost가 작은 간선을 하나씩 제거하는 것이 아니라, Cost가 가장 큰 간선부터 하나씩 간선을 추가한다고 생각을 하면 간선을 하나 추가하고, 그 두 정점만 Union-Find 기법으로 Grouping 해주면 되므로 시간 복잡도를 줄일 수 있습니다.

→ 간선을 추가했을 때, 경로가 생기는지 보자!

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int MOD = 1000000000;
int N, M, x, y, cost;
int root[100001], setSize[100001];
priority_queue<pair<int, pair<int, int>>> edge;

int find(int num) {
	if (num == root[num])
		return num;
	return root[num] = find(root[num]);
}

void merge(int num1, int num2) {
	root[num2] = num1;
	setSize[num1] += setSize[num2];
	setSize[num2] = 1;
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i <= N; i++) {
		root[i] = i;
		setSize[i] = 1;
	}

	long long total = 0;
	for (int i = 0; i < M; i++) {
		cin >> x >> y >> cost;
		edge.push({ cost,{x,y} });
		total += cost;
	}

	long long result = 0;
	for (int i = 0; i < M ; i++){
		pair<int, pair<int, int>> temp = edge.top();
		edge.pop();
		int pNum1 = find(temp.second.first);
		int pNum2 = find(temp.second.second);
		int curCost = temp.first;
		//둘이 같은 집합이 아닌 경우
		if (pNum1 != pNum2){
			result += (((1L * setSize[pNum1] * setSize[pNum2]) % MOD) * total) % MOD;
			result %= MOD;
			//같은 집합으로 합친다
			merge(pNum1, pNum2);
		}
		total -= curCost;
	}
	cout << result << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/7579

[ 알고리즘풀이 ]

memory[N] := N번 째 앱의 메모리

cost[N] := N번 째 앱의 비용

1) 메모리를 기준으로 한 1차원 DP 정의.

dp[M] := 메모리 M을 사용했을 때, 최소 비용

→ dp[M] = min ( dp[M], dp[M - memory[i]] + cost[i] );

dp 배열을 채우는데 N개의 물건을 하나씩 추가해가며 dp배열을 탐색해야하므로 O(N * sum of Memory)의 시간 복잡도를 가진다. 최악의 경우 100 * 10,000,000 으로 아마 백준 테스트케이스 중에 하드한게 없어서 시간초과 문제에 걸리지 않은 것 같다.

#include<iostream>
#include<algorithm>
#define INF 99999999
using namespace std;

int N, M, memory[100] = {}, cost[100] = {}, s = 0;
int dp[10000001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		cin >> memory[i];
		s += memory[i];
	}

	for (int i = 0; i < N; i++)
		cin >> cost[i];

	for (int i = 0; i <= s; i++)
		dp[i] = INF;

	dp[0] = 0, dp[memory[0]] = cost[0];

	for (int i = 1; i < N; i++) {
		for(int j = s; j >= memory[i]; j--)
			dp[j] = min(dp[j], dp[j - memory[i]] + cost[i]);
	}

	int ans = dp[M];
	for (int j = M; j <= s; j++)
		ans = min(ans, dp[j]);

	cout << ans;
}

2) 물건과 코스트를 기준으로 한 2차원 DP 정의.

dp[N][K] := 1 ~ N 번까지 물건을 사용해 코스트가 K일 때 최대 메모리.

→ dp[N][K] := max( dp[N - 1][K] , dp[N - 1][K - cost[i]] + memory[i] );

dp 배열을 채우는데 N개의 물건을 하나씩 추가해가며 dp배열을 탐색해야하므로 O(N * sum of Cost)의 시간 복잡도를 가진다. 따라서, 위의 1) 알고리즘보다 훨씬 좋은 시간 복잡도를 가진다.

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int N, M, memory[100] = {}, cost[100] = {}, s;
int dp[100][10001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> memory[i];

	for (int i = 0; i < N; i++){
		cin >> cost[i];
		s += cost[i];
	}

	memset(dp, 0, sizeof(dp));


	dp[0][cost[0]] = memory[0];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= s; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j - cost[i] >= 0)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + memory[i]);
		}
	}
	for (int j = 0; ; j++) {
		if (dp[N - 1][j] >= M) {
			cout << j;
			break;
		}
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/1351

[ 알고리즘풀이 ]

 전형적인 DP 문제지만 N이 너무 크므로 모든 부분에 값을 저장해서 쌓아가면 안되고, 점화식을 보면 DP[N] 은 P, Q가 제일 작은 2라고 반씩 크기가 줄어드므로 적당한 범위까지만 수열 값을 저장하고 난 후 재귀식으로 DP[N] 값을 구하면 쉽게 해결할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std;

const long long MAX = 10000000;
long long N, P, Q, dp[MAX + 1];

long long DP(long long N) {
	if (N <= MAX)
		return dp[N];
	return DP(N / P) + DP(N / Q);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	dp[0] = 1;
	cin >> N >> P >> Q;

	long long k = min(N, MAX );

	for (long long i = 1; i <= k; i++)
		dp[i] = dp[i / P] + dp[i / Q];

	cout << DP(N);

	return 0;
}

문제 : https://www.acmicpc.net/problem/1167

[ 알고리즘 풀이 ]

가장 긴 트리의 지름을 정하는 두 노드는 리프 노드다. ( 리프 노드가 아니면, 더 갈 수 있으므로 최대 지름일 수가 없다. ) 따라서, 우리는 리프 노드 2개를 골라 탐색을 하며 거리를 계산해봐야 되는데 이때, 모든 리프 노드 쌍에 대해서 탐색을 진행하면  정점이 100,000 개라 최악의 경우 (100,000)^2 번에 가까운 탐색이 진행돼 시간초과 문제에 걸리게 된다. 따라서, 임의의 리프 노드에서 BFS 탐색을 진행해 거리가 최대가 되는 순간의 리프 노드를 하나 찾고( 가장 긴 트리의 지름 중 하나의 노드 ) 다시 찾은 노드에서 BFS 탐색을 진행하면 가장 긴 트리의 지름을 찾을 수 있다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int V, s, x, y;
vector<pair<int, int>> graph[100001];
bool visited[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V;
	for (int i = 0; i < V; i++) {
		cin >> s;
		while (1) {
			cin >> x;
			if (x == -1)
				break;
			cin >> y;
			graph[s].push_back({ x,y });
			graph[x].push_back({ s,y });
		}
	}

	int start = 1;
	for (int i = 1; i <= V; i++) {
		if (graph[i].size() == 2){
			start = i;
			break;
		}
	}
	
	int ans = 0;
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = 1;

	int endNode = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		if (ans < cur.second) {
			endNode = cur.first;
			ans = cur.second;
		}

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	memset(visited, 0, sizeof(visited));
	q.push({ endNode, 0 });
	visited[endNode] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		ans = max(ans, cur.second);

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	cout << ans;
}