오늘의 문제
1005 ACM Craft
1029 그림 교환

1005 ACM Craft

코드

#include <bits/stdc++.h>
using namespace std;

int t, n, k, w;
int arr[1002], dp[1002];
vector<vector<int>> adj;

int dfs(int d) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	if (dp[d] != -1) return dp[d];
	if (adj[d].empty()) {
		dp[d] = arr[d];
		return dp[d];
	}
	int now = 0;
	for (int i : adj[d]) {
		now = max(now, dfs(i));
	}
	dp[d] = arr[d] + now;
	return dp[d];
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n >> k;
		adj = vector<vector<int>>(n, vector<int>(0, 0));
		fill(dp, dp + n, -1);
		for (int i = 0; i < n; i++) cin >> arr[i];
		while (k--) {
			int a, b;
			cin >> a >> b;
			adj[b - 1].emplace_back(a - 1);
		}
		cin >> w;
		cout << dfs(w - 1) << "\n";
	}
}

그래프를 역방향으로 만들었다.

1029 그림 교환

코드

시간 초과

#include <bits/stdc++.h>
using namespace std;

int n, arr[16][16], max_num;
int vis[16];

void dfs(int k, int p, int num) {
	if (k == n) {
		max_num = max(num, max_num);
		return;
	}
	vis[k] = 1;
	for (int i = 0; i < n; i++) {
		if (!vis[i] && arr[k][i] >= p) {
			dfs(i, arr[k][i], num + 1);
			vis[i] = 0;
		}
	}
	max_num = max(max_num, num);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j] - '0';
		}
	}
	dfs(0, 0, 1);
	cout << max_num;
}

처음에 dfs만 이용해서 풀었는데, 시간 초과가 발생했다. 당연히 중복 연산이 많았겠지.. 라고 생각하며 해당 코드에 dp를 적용하려고 했는데..??

도무지 모르겠어서 구글링으로 참고했다!! 그랬더니 방문한 사람을 비트 마스크를 이용해서 푸는 방법을 이용하더라. 방문을 표시할 필요가 있고, 사람 수가 적은 경우는 비트 마스크를 사용할 수 있다는 것을 배웠다.

비트 마스크 이용 및 성공

#include <bits/stdc++.h>
using namespace std;

int n, arr[16][16], dp[16][10][1 << 16];

int dfs(int k, int p, int vis) {
	int& ret = dp[k][p][vis];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < n; i++) {
		if (!(vis & (1 << i)) && arr[k][i] >= p) {
			int nv = vis | (1 << i);
			ret = max(ret, dfs(i, arr[k][i], nv) + 1);
		}
	}
	return ret;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j] - '0';
		}
	}
	memset(dp, -1, sizeof(dp));
	dfs(0, 0, 1);

	cout << dp[0][0][1] + 1;
}

비트 마스크 이용하는 문제들을 더 풀어봐야겠다.