Codetesing의 코딩공부

union-find , graph 문제이다.

union-find로 풀 경우, 들어오는 대로 union하여 그룹을 만든후, 그룹의 수를 세면 된다.

graph로 풀 경우, 양방향 그래프를 만들어 준 후, dfs 탐색 하여 그룹의 수를 확인한다.

여기 코드는 graph로 풀은 경우이다.

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

using namespace std;

bool visited[101];

void DFS(vector<vector<int>> G, int index)
{
	visited[index] = true;
	for (int i = 0; i < G[index].size(); i++)
		if (!visited[G[index][i]])
			DFS(G, G[index][i]);
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(visited, false, sizeof(visited));
		int N, M; cin >> N >> M;
		vector<vector<int>> GRAPH(N + 1, vector<int>());
		int start, end, out = 0;
		for (int i = 0; i < M; i++)
		{
			cin >> start >> end;
			GRAPH[start].push_back(end);
			GRAPH[end].push_back(start);
		}

		for(int i = 1; i <= N; i++)
			if (!visited[i])
			{
				out++;
				DFS(GRAPH, i);
			}

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

탐색으로 풀면 TL이 남.

내림차순으로 sort해서 3개씩 묶어 계산하면 됨.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool compare(int a, int b)
{
	return a > b;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		long long ans = 0;
		int N; cin >> N;
		vector<int> value(N);
		for (int i = 0; i < N; i++)
			cin >> value[i];

		sort(value.begin(), value.end(), compare);

		for (int i = 0; i < N; i += 3)
		{
			ans += value[i];
			if (i + 1 < N)
				ans += value[i + 1];
		}

		cout << '#' << test_case << ' ' << ans << '\n';
	}
	return 0;
}

비트마스크 DP 를 이용하였으며 DFS로 탐색하였음.

#include<iostream>
#include<cstring>

using namespace std;

int N, M;
long long list[17];
long long DP[1 << 17];

long long DFS(int index)
{
	if (index == (1 << (N + 1)) - 2)
		return 1;
	if (DP[index] != 0)
		return DP[index];

	for (int i = 1; i <= N; i++)
	{
		if ((index & 1 << i) > 0)
			continue;
		if ((index & list[i]) != list[i])
			continue;
		DP[index] += DFS(index | 1 << i);
	}

	return DP[index];
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(list, 0, sizeof(list));
		memset(DP, 0, sizeof(DP));

		cin >> N >> M;

		int start, end;
		for (int i = 0; i < M; i++)
		{
			cin >> start >> end;
			list[end] = list[end] | (1LL << start);
		}
		
		long long out = DFS(0);

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

DP문제이다. 점화식만 찾으면 되는데 쉽지는 않았다.

#define MAX 1000000007

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;
	long long FACT[1001] = { 0, 1 };
	long long DP[1001] = { 0 };
	int max_ind = 0;

	for (int i = 2; i <= 1000; i++)
		FACT[i] = (FACT[i - 1] * i) % MAX;
	
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N; cin >> N;
		if (N != 1 && DP[N] == 0)
		{
			for (int i = max_ind + 1; i <= N; i++)
				DP[i] = (i * DP[i - 1] + (i / 2) * FACT[i - 1]) % MAX;
			max_ind = N;
		}

		cout << '#' << test_case << ' ' << DP[N] << '\n';
	}
	return 0;
}

쉬운 문제였다.

S와 단어의 길이가 다르면 false이고 아니라면 확인 해주면 된다.

key와 단어가 같은지 확인할때, 단어의 글자를 키패드의 숫자로 바꾼 후, S와 같은지 확인하면 된다.

키패드의 숫자로 바꿀때,  pqrs를 못보고 z를 예외처리한 후, / 3으로 나누는법을 사용했다가 틀렸다.

#include<iostream>
#include<string>
#include<vector>

using namespace std;

char TRANS(char a)
{
	if ((a == 'a') || (a == 'b') || (a == 'c'))
		return '2';
	if ((a == 'd') || (a == 'e') || (a == 'f'))
		return '3';
	if ((a == 'g') || (a == 'h') || (a == 'i'))
		return '4';
	if ((a == 'j') || (a == 'k') || (a == 'l'))
		return '5';
	if ((a == 'm') || (a == 'n') || (a == 'o'))
		return '6';
	if ((a == 'p') || (a == 'q') || (a == 'r') || (a == 's'))
		return '7';
	if ((a == 't') || (a == 'u') || (a == 'v'))
		return '8';
	if ((a == 'w') || (a == 'x') || (a == 'y') || (a == 'z'))
		return '9';
}

bool IS_VOCA(string key, string voca)
{
	if (key.size() != voca.size())
		return false;

	for (int i = 0; i < key.size(); i++)
	{
		if (key[i] == 1)
			return false;

		if (key[i] != TRANS(voca[i]))
			return false;
	}
	return true;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		string S; cin >> S;
		int N; cin >> N;
		vector<string> voca(N);
		for (int i = 0; i < N; i++) cin >> voca[i];

		int out = 0;
		for (int i = 0; i < N; i++)
			if (IS_VOCA(S, voca[i]))
				out++;

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}