[210720] 제3회 류호석배 알고리즘 코딩테스트 후기

백준 플랫폼에서 류호석배 알고리즘 코딩테스트가 열려 있어서 한번 참가해보았다.

https://www.acmicpc.net/contest/view/666

제3회 류호석배 알고리즘 코딩 테스트

당시에 4문제를 해결하였고, 3번이 꽤나 어려웠던 기억이 있다.

중간중간에 저녁식사, 운동 등으로 잠깐 탈주했긴 했는데, 5시간 풀집중했어도 3번을 해결할 수 있었을지는 미지수.

 

다음날에 난이도 티어를 구경해봤는데 생각보다 높게 매겨져 있어서 놀랐던 문제셋이었다.

나는 대체로 다른 사람들에 비해 티어를 좀 후하게 주는 편 (의도한 것이 아니다) 이었는데, 이번엔 내가 다른 사람들에 비해 박하게 티어를 매긴 편이었어서 놀랐다.

 

문제는 역시 알고리즘 대가인 분께서 출제하셔서 그런지 꽤 괜찮았었고, 전형적인 문제도 있었지만, 적절한 구현량을 요구하는 재밌는 시뮬레이션 문제도 꽤 있었어서 만족스러웠던 대회였다.

 

밑에 간단하게 후기를 남겨보겠다.

---

1. 빌런 호석

22251번: 빌런 호석

위와 같이 디지털 숫자로 표기되는 형태를 7세그먼트 디스플레이라 불린다.

은근히 자주 나오는 것 같다.

처음에는 획변화를 일일이 구함으로써 시간이 꽤 오래 소요됐으나, 한번 WA를 받고 나서 구글에 디지털 숫자 획 개수 차이로 검색해보니 7세그먼트 디스플레이 관련 포스팅이 나와 생각보다 웰노운임을 깨닫고 기록해두려고 한다.

 

int p2[10][8] = {
{0, 0, 0, 0, 0, 0, 1, 1}, //0
{1, 0, 0, 1, 1, 1, 1, 1}, //1
{0, 0, 1, 0, 0, 1, 0, 1}, //2
{0, 0, 0, 0, 1, 1, 0, 1}, //3
{1, 0, 0, 1, 1, 0, 0, 1}, //4
{0, 1, 0, 0, 1, 0, 0, 1}, //5
{0, 1, 0, 0, 0, 0, 0, 1}, //6
{0, 0, 0, 1, 1, 1, 1, 1}, //7
{0, 0, 0, 0, 0, 0, 0, 1}, //8
{0, 0, 0, 0, 1, 0, 0, 1} //9
};

위와 같이 7세그먼트 디스플레이 획개수 코드를 미리 알고있으면 편할 듯 하여 기록한다.

맨 위에서부터 시계방향 순서로 획 표기 순서이며, 가운데 획은 6번째 인덱스, 그리고 7번째 인덱스는 항상 1로 표기된다. 0이 켜짐, 1이 꺼짐이다. 맨 오른쪽은 저항을 의미하는 것으로 기억하고 있다.

 

아무튼 위 배열을 이용해 두 숫자 사이의 차잇값을 이용하여 브루트포스를 돌리면 간단하게 풀린다.

다른 구현 문제들에 비해 구현량이 많지 않고, 크게 복잡하지 않은 듯한데 G5 티어를 받아 꽤 놀랐던 문제.

다만, 처음 봤을 때 획변화량을 일일이 구해야된다는 것에 킬링타임 문제라 판단하여 넘기고 2번으로 넘겼던 기억이 있긴 하다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1000001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, K, P, X, d[MAX], ans, p[10][10];
int p2[10][8] = {
{0, 0, 0, 0, 0, 0, 1, 1}, //0
{1, 0, 0, 1, 1, 1, 1, 1}, //1
{0, 0, 1, 0, 0, 1, 0, 1}, //2
{0, 0, 0, 0, 1, 1, 0, 1}, //3
{1, 0, 0, 1, 1, 0, 0, 1}, //4
{0, 1, 0, 0, 1, 0, 0, 1}, //5
{0, 1, 0, 0, 0, 0, 0, 1}, //6
{0, 0, 0, 1, 1, 1, 1, 1}, //7
{0, 0, 0, 0, 0, 0, 0, 1}, //8
{0, 0, 0, 0, 1, 0, 0, 1} //9
};
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K >> P >> X;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (i == j)
				continue;
			int ret = 0;
			for (int k = 0; k < 8; k++) {
				if (p2[i][k] != p2[j][k])
					ret++;
			}
			p[i][j] = ret;
		}
	}
	string s = to_string(X);
	for (int i = 1; i <= N; i++) {
		if (X == i)
			continue;
		string num = to_string(i);
		for (int j = K - 1; j >= 0; j--) {
			int n1, n2;
			if (j >= s.size())
				n1 = 0;
			else
				n1 = s[s.size() - j - 1] - '0';
			if (j >= num.size())
				n2 = 0;
			else
				n2 = num[num.size() - j - 1] - '0';
			d[i] += p[n1][n2];
		}
		if (d[i] <= P)
			ans++;
	}
	cout << ans << "\n";
}

---

2. 정보 상인 호석

22252번: 정보 상인 호석

상위 b개의 정보를 구매하고, 고릴라의 이름이 문자열로 나타나므로 우선순위 큐와 map을 이용하여 적절히 처리한다.

이 때, 상위 b개의 정보구매를 위해 우선순위 큐를 이용한다.

우선순위 큐의 삽입 및 삭제 시간복잡도는 O(lgN)이므로 이 문제의 시간복잡도는 O(QlgK)이며, lg(1e6)은 약 20이므로 충분히 시간 내에 해결가능하다. 참고로 lg(1e3)은 약 10이다.

처음엔 시간복잡도를 잘못 계산해 O(QK)인 줄 알고 그냥 믿음을 가지고 제출했는데, 알고보니 우선순위큐의 삭제, 삽입으로 진행되므로 생각보다 간단했던 문제. 또한, 가장 먼저 AC받은 문제이기도 했다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int Q;
priority_queue<ll> pq[MAX];
map<string, int> m;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> Q;
	ll ans = 0;
	for (int i = 0; i < Q; i++) {
		int ch, k;
		string s;
		cin >> ch >> s >> k;
		m.insert({ s, m.size()+1 });
		if (ch == 1) {
			for (int i = 0; i < k; i++) {
				ll n;
				cin >> n;
				pq[m[s]].push(n);
			}
		}
		else {
			if (m[s]==0)
				continue;
			int j = 0;
			while (!pq[m[s]].empty() && j<k) {
				ans += pq[m[s]].top();
				pq[m[s]].pop();
				j++;
			}
		}
	}
	cout << ans << "\n";
}

---

3. 트리 디자이너 호석

22253번: 트리 디자이너 호석

개인적으로 가장 어렵다고 느껴지는 문제.

간단하게 해결될 줄 알았으나 O(NlgN) 이하의 시간복잡도 풀이는 커녕 O(N^2) 풀이도 떠오르지 않아 패스했다가 결국 대회 내에서 AC받지 못했던 문제이다. dfs로 접근했다가 어떤 노드를 선택하느냐에 따라 답이 달라져 트리dp 느낌이 물씬 났지만 잘 생각나지 않아 일단 패스했던 문제.

 

잘 생각해보면 숫자가 0~9까지 가능하고,

루트에서 리프까지 이동하여 확인하므로 단방향으로 트리를 바꾸어준 다음에,

특정 노드를 선택할 경우, 그 노드의 값보다 크거나 같은 노드들을 선택하는 경우로, 

특정 노드를 선택하지 않을 경우, 다음 노드로 dp처리해주는 경우로 처리해주면 된다.

 

트리dp는 선택 or 미선택으로 인해 두 번 왔다갔다 해야되므로 단방향 트리로 변경해주던지, 아니면 그때그때 visit처리를 유연하게 해주던지 자신의 입맛에 맞게 잘 구현하자.

 

시간복잡도는 O(10*N*알파)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
ll N, a[MAX], d[MAX][10], ans;
vector<int> v[MAX], k[MAX];
bool visit[MAX];
void init(int cur) {
	visit[cur] = true;
	for (auto i : v[cur]) {
		if (!visit[i]) {
			k[cur].push_back(i);
			init(i);
		}
	}
}
ll dp(int cur, int n) {
	ll& ret = d[cur][n];
	if (ret != -1)
		return ret;
	ret = 0;
	if (a[cur] == n)
		ret++;
	for (auto i : k[cur]) {
		ret += dp(i, n);
		ret %= MOD;
		if (a[cur] == n) {
			for (int j = n; j < 10; j++) {
				ret += dp(i, j);
				ret %= MOD;
			}
		}
	}
	return ret % MOD;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < N - 1; i++) {
		int b, c;
		cin >> b >> c;
		v[b].push_back(c);
		v[c].push_back(b);
	}
	init(1);
	memset(d, -1, sizeof(d));
	for (int i = 0; i < 10; i++) {
		ans += dp(1, i);
		ans %= MOD;
	}
	cout << ans << "\n";
}

---

4. 공정 컨설턴트 호석

22254번: 공정 컨설턴트 호석

2번을 풀고 3번이 생각보다 어려워 4번으로 넘어가 AC를 받은 문제이다. 즉, 대회 내에서 두번째로 해결한 문제.

전형적인 이분탐색 문제이다. 공장 라인의 최소 개수로 가능한 값을 이분탐색으로 구해준다.

이 때, 이분탐색 내의 구현에서 우선순위 큐가 들어가는데,

그 이유는 공정이 이뤄지는 규칙 때문이다.

 

시간복잡도는 O((NlgN)lgK)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, X, a[MAX], ans = INF;
vector<int> v;
void solve(int s, int e) {
	while (s <= e) {
		int mid = (s + e) / 2;
		bool flag = true;
		priority_queue<pi, vector<pi>, greater<pi>> pq;
		for (int i = 1; i <= mid; i++) {
			pq.push({ 0, i });
		}
		for (int i = 0; i < N; i++) {
			int cur = pq.top().second;
			int cost = pq.top().first;
			pq.pop();
			if (cost + a[i] <= X)
				pq.push({ cost + a[i], cur });
			else {
				flag = false;
				break;
			}
		}
		if (!flag)
			s = mid + 1;
		else {
			ans = mid;
			e = mid - 1;
		}
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	int s = 1, e = 100000;
	solve(s, e);
	cout << ans << "\n";
}

s=0, e=1e6으로 놓고 돌리면 당연히 틀린다.

최소 1개는 있어야 하기 때문.

---

5. 호석사우루스

22255번: 호석사우루스

처음에 BFS가 생각났으나, 충격량이 단일값이 아니기 때문에 dijkstra로 방법을 바꾸었다.

또한, 이동방향이 달라지는 3가지 경우가 존재하기 때문에,

이 3가지 경우에 해당하는 이동가능 경우가 달라지기 때문에 d[y][x][3]으로 충격량을 메모이제이션하여 해결해야 되는 문제. 그 외에 범위를 조심하고 이동방향이 달라지는 것을 주의하면 전형적인 다익스트라로 해결된다.

이 문제 또한 생각보다 티어가 높아서 놀랐다. 다익스트라 기본형이 G4~G5인 걸 감안해서 G3 정도일 줄 알았는데 G2 티어를 받은 문제.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<pi, pi> pii;
const int MAX = 101;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M, Sx, Sy, Ex, Ey, a[MAX][MAX], d[MAX][MAX][3];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
vector<int> v;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	cin >> Sx >> Sy >> Ex >> Ey;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> a[i][j];
		}
	}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({ {0, 1}, {Sy, Sx} });
	memset(d, INF, sizeof(d));
	d[Sy][Sx][1] = 0;
	while (!pq.empty()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		int k = pq.top().first.second;
		int cost = pq.top().first.first;
		pq.pop();
		if (y == Ex && x == Ey) {
			cout << cost << "\n";
			return 0;
		}
		if (d[y][x][k%3] < cost)
			continue;
		for (int i = 0; i < 4; i++) {
			if (k % 3 == 1 && i >= 2)
				continue;
			if (k % 3 == 2 && i < 2)
				continue;
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx > 0 && ny > 0 && nx <= M && ny <= N) {
				int nCost = a[ny][nx] + cost;
				if (a[ny][nx] == -1)
					continue;
				if (nCost < d[ny][nx][(k+1)%3]) {
					d[ny][nx][(k+1)%3] = nCost;
					pq.push({ {nCost, k + 1}, {nx, ny} });
				}
			}
		}
	}
	cout << -1 << "\n";
}

---

요즘 실전 대회에 참여하는 것이 재밌기도 하고 실력상승에도 많이 도움이 되는 듯하여

최대한 많이 참여해보고있다.

이번 대회를 통해 7세그먼트 디스플레이, 우선순위 큐 시간복잡도, 트리dp에 대해 재점검하는 시간을 가졌고, 

재점검하면서, 그리고 문제를 풀면서 얻은 것들이 많아 만족스러운 대회였다