[BOJ/C++] shake! 2021 A ~ D번 (BOJ 24228, 24229, 24230, 24231)

요즘 너무 바쁘다.

게임 엔진 건드릴 시간이 없다...

 

아무튼, shake 2021의 문제를 풀어봤습니다.

Open Contest에서는 D번까지 풀었고, 그 뒤로는... 나중에 풀어봐야겠습니다.

시간이 부족행

 

BOJ 24228. 젓가락

문제 링크 : https://www.acmicpc.net/problem/24228

24228번: 젓가락

풀이 : 젓가락이 한 쌍 완성되기 위한 최악의 경우는,

모든 젓가락을 하나씩 뽑은 뒤에 아무 젓가락이나 하나 뽑는 경우입니다. 이 때 뽑는 갯수는 $N + 1$개입니다.

그 이후엔 방금 완성한 한 쌍을 다시 뽑는 경우 (2개)와, 나머지 젓가락 중 한 쌍을 완성하는 경우 (1개)로 나뉩니다.

다시 말해서 최악의 경우는 모든 젓가락을 하나씩 뽑고, 그 이후로는 특정 젓가락만을 계속 뽑는 경우가 됩니다.

 

따라서 처음 한 쌍을 완성하기 위한 $N + 1$개, 그 이후로 $R - 1$개의 쌍을 완성하기 위한 $2 \times(R - 1)$개를 뽑아야 하므로, $N + 2R - 1$을 출력하면 됩니다.

$N, R$의 범위가 $10^{18}$이므로, long long을 사용해야 합니다.

#include <iostream>
#include <algorithm>

using namespace std;

long long N, R;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> R;

	cout << N + 2 * R - 1;
	return 0;
}

 

BOJ 24229. 모두싸인 출근길

문제 링크 : https://www.acmicpc.net/problem/24229

24229번: 모두싸인 출근길

풀이 : $N \le 200000$이므로, 간단하게 왼쪽부터 해당 판자에서 이동할 수 있는 최대 거리를 계산해 나가면 됩니다.

편의를 위해 연결된 판자는 모두 하나로 합치고, 해당 판자에 도달할 수 없다면 탐색을 멈추면 됩니다.

 

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

using namespace std;

typedef pair<int, int> p;

const int MAX = 1e9 + 5;
int N, ans;
p line[200001];
vector<p> v;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) cin >> line[i].first >> line[i].second;

	sort(line, line + N);

	v.push_back(line[0]);

	for (int i = 1; i < N; i++)
		if (v.back().second >= line[i].first)
			v.back().second = max(v.back().second, line[i].second);
		else
			v.push_back(line[i]);

	N = v.size();

	for (int i = 0; i < N && i <= ans; i++)
	{
		p P = { v[i].second * 2 - v[i].first, MAX };
		auto it = upper_bound(v.begin(), v.end(), P);
		it--;
		ans = max(ans, (int)(it - v.begin()));
	}

	cout << v[ans].second;
	return 0;
}

 

24230. 트리 색칠하기

문제 링크 : https://www.acmicpc.net/problem/24230

24230번: 트리 색칠하기

풀이 : 부모 노드가 색칠되면, 자식 노드도 모두 색칠됩니다.

따라서 부모 노드를 먼저 색칠한 뒤에, 자식 노드를 색칠해야 합니다.

부모 노드부터 그래프 탐색을 시작해서, 부모 노드와 자식 노드의 색이 다르다면 횟수를 1 올리고

그 자식 노드에 대해서 그래프 탐색을 실행하면 됩니다.

 

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

using namespace std;

int N, color[200001], a, b;
vector<int> graph[200001];
bool v[200001];

int dfs(int node, int c)
{
	int ret = color[node] != c;
	v[node] = 1;

	for (int& adj : graph[node])
		if (!v[adj]) ret += dfs(adj, color[node]);

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++) cin >> color[i];

	for (int i = 1; i < N; i++)
	{
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	cout << dfs(1, 0);
	return 0;
}

 

24231. 해석

문제 링크 : https://www.acmicpc.net/problem/24231

24231번: 해석

풀이 : 구간 $[L, R]$에 존재하는 문자열의 갯수를 생각해봅시다.

$L < i < R$인 $S[L] \neq S[i]$를 만족하는 모든 $i$에 대한 구간 $[L + 1, i - 1]$의 문자열 갯수 * $[i + 1, R]$의 문자열 갯수를 더하면 됩니다.

점화식으로 나타내면 다음과 같습니다.

$C[L, R] = \sum_{L<i<R} C[L + 1, i - 1] \times C[i + 1, R]$

갯수를 곱하므로, 빈 문자열의 경우 ($L \ge R$)엔 1을 반환해야 합니다.

 

모듈러 연산을 하긴 하지만, 점화식에서 곱이 최대 $10^{18}$ 정도까지 나올 수 있어서, long long을 사용했습니다.

그리고 연산 횟수가 많아 시간 초과가 날 수 있으므로, 메모이제이션 등을 사용해서 이미 구한 구간은 넘어갈 수 있도록 처리해줘야 합니다. 계산하지 않은 경우엔 -1, 계산한 경우엔 0부터 시작하도록 처리했습니다.

 

참고로 문자열의 길이가 홀수라면 올바른 문자열이 존재할 수 없습니다.

처음부터 길이가 홀수라면 바로 0을 출력하면 되고, 점화식을 계산할 때 $i$를 2씩 증가시켜도 됩니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
string S;
ll d[301][301];

ll getCount(int L, int R)
{
	if (L >= R) return 1;

	ll& ret = d[L][R];
	if (ret >= 0) return ret;
	ret = 0;

	for (int i = L + 1; i <= R; i += 2)
		if (S[L] != S[i]) ret = (ret + getCount(L + 1, i - 1) * getCount(i + 1, R)) % MOD;

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	memset(d, -1, sizeof(d));
	cin >> S;

	if (S.size() % 2) cout << 0;
	else
		cout << getCount(0, S.size() - 1);
	return 0;
}

 

E번부터는 언젠가 시도해보고, 되면 관련 포스팅을 새로 올리겠습니다.

근데 아마 안 해볼 것 같음 ㅋㅋ;

 

p.s. 2022.03.12 추가) 아니 이걸 풀었네 ㅋㅋ