2024-03-03

-돌 게임 3(9657, 백준)

 간단한 DP문제였다. 돌게임1과 똑같이 풀면 된다. 그냥 마지막 돌을 가져간 사람이 이김으로, 마지막 돌을 1로 두고 마지막 돌애서부터 1개 또는 3개 또는 4개 전의 돌중 하나라도 가져가면 지게 됨으로 0으로 두는 식으로 점화식을 세우면 O(N)만에 풀 수 있다. 이 문제도 수학으로 풀릴까 궁굼하다. 다음번에 돌게임 시리즈를 올려봐야겠다. 

>점화식<

if (dp[i + 1] == 0) dp[i] = 1;
if (i + 3 <= n && dp[i + 3] == 1) dp[i] = 0;
if (i + 4 <= n && dp[i + 4] == 1) dp[i] = 0;

<소스 코드>

#include <stdio.h>
#include <algorithm>

int n;
int dp[1010];

int main()
{
	int i, j;
	scanf("%d", &n);
	dp[n] = 1;
	for (i = n - 1; i >= 1; i--) {
		if (dp[i + 1] == 0) dp[i] = 1;
		if (i + 3 <= n && dp[i + 3] == 1) dp[i] = 0;
		if (i + 4 <= n && dp[i + 4] == 1) dp[i] = 0;
	}
	if (dp[1] == 1 || dp[3] == 1 || dp[4] == 1) printf("SK");
	else printf("CY");
}

-동전2(2294, 백준)

 정말로 잘 알려진 DP문제다. 그래서 그런지 풀이법이 바로 떠올라서 풀었다. 현재의 값에서부터 갖고있는 동전의 가치 전의 값의 + 1중 최소의 값이 가지고 있는 동전으로 현재값을 만드는 최소 개수가 된다. 즉 Dp[i] = 가지고있는 동전으로 i원을 만들 때 필요한 최소 동전의 갯수로 두고 생각하면 점화식이 간단히 나온다.

>점화식<

if (i >= arr[j]) dp[i] = min(dp[i], dp[i - arr[j]] + 1);

<소스 코드>

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, k;
int arr[110];
int dp[10010];

int main()
{
	int i, j;
	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	for (i = 1; i <= k; i++) dp[i] = 2e9;
	for (i = 1; i <= k; i++) {
		for (j = 0; j < n; j++) {
			if (i >= arr[j]) dp[i] = min(dp[i], dp[i - arr[j]] + 1);
		}
	}
	if (dp[k] >= 2e9) printf("-1");
	else printf("%d", dp[k]);
	return 0;
}

-숫자카드(2591, 백준)

 암호코드(#2011)과 비슷한 문제이다. 역시 사이에 끼인 0을 처리하는게 굉장히 까다롭다. 사이에 끼인 0만 처리할 수 있다면, 간단한 피보나치의 점화식이 나온다. 바로전 카드까지를 만드는 경우에 카드하나를 추가해서 현재 값을 만들 수 있음으로, 바로 전값을 가져온다. 두자리수카드가 34까지밖에 없음으로, 카드 두개를 합쳐서 34보다 작거나 같은 수를 만들 수 있다면, 그 전전값에서도 가져올 수 있다. 여기에 사이에 끼인 0만처리하면 간단히 풀린다.

>점화식<

Dp[i] = Dp[i-1] + Dp[i-2];

<소스코드>

#include <stdio.h>
#include <string.h>

using namespace std;

char s[50];
int dp[50], x;

int main()
{
	int i, j;
	scanf("%s", s + 1);
	if (s[1] == '0') {
		printf("0");
		return 0;
	}
	s[0] = '0';
	x = strlen(s) - 1;
	dp[0] = 1;
	dp[1] = 1;
	for (i = 2; i <= x; i++) {
		int a = s[i - 1] - '0';
		int b = s[i] - '0';
		if (b > 0) dp[i] += dp[i - 1];
		if (a == 0) continue;
		if (a * 10 + b <= 34) dp[i] += dp[i - 2];
	}
	printf("%d", dp[x]);
	return 0;
}

-거짓말(1043, 백준)

 저번에 BFS로 풀었는데, 정해가 유니온 파인드(Disjiont_set, 분리집합)이라고해서 유니온 파인드를 이용하여 풀어보았다. 각 모임에 참여한 모든 사람들을 하나의 집합으로 묶은 뒤, 첫번째 회의부터 차례로 검사해가며, 만약 회의에 한명도 거짓말한 사람과 같은 집합에 속해있지 않으면, ans++을 하는 식으로 구현했다. 뇌빼고 구현한 것같은데 그냥 되서 기분이 좋았다.

<소스코드>

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int par[110];
vector<int> L;
vector<int> vec[110];

int ffind(int x)
{
	if (x == par[x]) return x;
	else return par[x] = ffind(par[x]);
}

void funion(int x, int y)
{
	int a = ffind(x);
	int b = ffind(y);
	if (a == b) return;
	else par[b] = a;
}

int main()
{
	int i, j;
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for (i = 1; i <= n; i++) par[i] = i;
	for (i = 0; i < k; i++) {
		int x;
		scanf("%d", &x);
		L.push_back(x);
	}
	for (i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		for (j = 0; j < x; j++) {
			int y;
			scanf("%d", &y);
			vec[i].push_back(y);
		}
		for (j = 0; j < x - 1; j++) {
			funion(vec[i][j], vec[i][j + 1]);
		}
	}
	int ans = 0;
	for (i = 0; i < m; i++) {
		int che = 0;
		for (j = 0; j < vec[i].size(); j++) {
			for (int l = 0; l < k; l++) {
				if (ffind(L[l]) == ffind(vec[i][j])) che = 1;
			}
		}
		if (che == 0) ans++;
	}
	printf("%d", ans);
	return 0;
}

-친구 네트워크(4195, 백준)

 맵과 셋 자료구조를 이용하여, 친구관계인 모든 경우를 저장한 후, 주어진 사람의 수(노드의 수)만큼 par배열을 초기화 시키고, 저장한 친구관계를 모두 union해주며, 집합의 크기를 계산하여 출력하는 유니온 파인드 문제였다. 집합의 크기를 구하는 방법이 생각이 안나서 처음에는 O(N^2)으로 풀었다가 당연히 시간초과가 나왔고, 좀더 생각해본 결과 cnt배열을 만들어 1로 초기화 시킨 뒤, 합칠때, cnt배열을 같이 더해주는 식으로 집합의 크기를 구했다. (틀릴까봐 C++ 입출력 속도를 높였다.)

<소스코드>

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

int par[200010];
vector <pair<string, string>> vec;
int cnt[200010];

int ffind(int x)
{
	if (par[x] == x) return x;
	else return par[x] = ffind(par[x]);
}

void funion(int x, int y)
{
	int a = ffind(x);
	int b = ffind(y);
	if (a == b) return;
	else {
		par[b] = a;
		cnt[a] += cnt[b];
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		int idx = 1;
		int n;
		cin >> n;
		set <string> st;
		map <string, int> mp;
		for (int i = 0; i < n; i++) {
			string s1, s2;
			cin >> s1 >> s2;
			if (st.find(s1) == st.end()) st.insert(s1), mp.insert({ s1, idx++ });
			if (st.find(s2) == st.end()) st.insert(s2), mp.insert({ s2, idx++ });
			vec.push_back({ s1, s2 });
		}
		for (int i = 1; i <= idx; i++) par[i] = i, cnt[i] = 1;
		for (int i = 0; i < vec.size(); i++) {
			funion(mp[vec[i].first], mp[vec[i].second]);
			int x = ffind(mp[vec[i].first]);
			cout << cnt[x] << '\n';
		}
		vec.clear();
		mp.clear();
		st.clear();
	}
	return 0;
}