[그룹연습] 제목을 뭘로 할지 모르겠는 Div.1 후기

210509 그룹 Div.1 대회에 응시하였다.

제1회 숙대 경진대회 Open Contest와 시간대가 겹쳐 아쉽긴 했지만,

숙대 경진대회 문제는 대회 이후에도 풀 수 있으므로

div.1 연습에 14~16시동안 응시하였다.

---

아래 그룹은 건국대 학생들끼리 코딩 실력을 키우기 위해 만들어진 그룹입니다.

격주로 시간 내에 문제를 푸는 연습을 대회처럼 진행하고 있습니다. (건국대 학생분들 가입 환영입니다~)

www.acmicpc.net/group/9928

소박하지만 그룹입니다

---

어려웠다. 근데 운이 좋았다.

내가 후기를 작성하는 날은 대회결과가 좋은 날

운좋게 맞은 문제들이 많아 복기 겸 풀이를 작성하려 한다.

---

A. 미로에 갇힌 상근

www.acmicpc.net/problem/5069

5069번: 미로에 갇힌 상근

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 15;
const int INF = 1e9 + 7;
int N, d[MAX] = { 0, 0, 6, 12, 90, 360, 2040,
10080, 54810, 290640, 1588356, 8676360, 47977776, 266378112,
1488801600 };
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--) {
		cin >> N;
		cout << d[N] << "\n";
	}
}

문제 출제의도는 dp 점화식을 구해서 풀으라는 문제였겠지만,

0,6,12,90 까지 일반항을 구한 후 수열 규칙 찾는 문제처럼 보여서 oeis.org 사이트에 돌려서 풀었다.

oeis.org 사이트에선 수열의 앞 항 몇개를 입력하면 규칙성에 따라 수열을 추리해준다.

진작 돌려서 풀걸

사실 점화식이 잘 보이지 않아 최후의 수단으로 돌린 것이다.

코딩테스트 및 대회에서 구글링 허용이 되는 점을 고려하여 oeis.org에 수열을 돌렸다.

A번은 쉬운 문제일텐데 안풀리면 말린다 생각하여 수열 돌린 후 14분정도 후 AC를 맞았다. (14:12에 대회를 시작하였다.)

그런데, 다른 분들 풀이를 보니까.. 굉장히 복잡하다. 3중, 4중 for문을 이용하여 푸신 분들도 있었다.

그냥 돌리길 잘한 듯 하다.

---

B. K-균등 문자열

www.acmicpc.net/problem/15502

15502번: K-균등 문자열

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 1001;
const int MOD = 1e9 + 7;
int N, M, p[MAX], ans = 1;
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	if (a > b)
		swap(a, b);
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		p[i] = i;
	}
	for (int i = 0; i < M; i++) {
		int L, R, K;
		cin >> L >> R >> K;
		for (int j = L; j + K <= R; j++) {
			merge(j, j + K);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (i == find(i))
			ans *= 2;
		ans %= MOD;
	}
	cout << ans << "\n";
}

개인적으로 되게 좋은 문제라 생각한다.

유니온파인드임을 꽁꽁 숨기는 문제이다. (유니온파인드 문제들이 쉬운 골드를 제외하곤 대체로 그렇다.) 

처음에 풀이 방법이 생각나지 않아 C번을 풀고 B번으로 넘어가서 고민하다가 AC를 맞은 문제인데,

어떤 상황이어야 K-균등 문자열이 될지 캐치해야 하는 문제이다.

 

K-균등 문자열이려면 아래와 같다.

L에서 1이라면, L+K에서도 1이어야 한다.

L+i에서 1이라면, L+K+i에서도 1이어야 한다.

예제 입력 1을 통해 살펴보자.

5 2
1 4 2
3 5 3

"00000"의 경우 당연히 예제 입력 조건에 부합한다.

"1xxxx" (x는 미지수)일 경우, 1~4구간에서 2-균등문자열이기 위해선 "1x1xx"이어야 하며,

"01xxx",일 경우, 주변 ~K-1까진 1이 있으므로 괜찮은데, 1이 나온 이후 K번째 오른쪽부터 균등문자열 조건이 성립하지 않는다. 이렇게 관찰을 통해 K-균등문자열이 성립할 조건을 찾아야 한다. 솔직히 증명은 나도 잘 모르겠다...

 

1. L과 L+K가 같아야 한다는 점,
2. 예제 입력 2에서 모든 수가 굳이 같을 필요가 없어 ans*=2를 계속 한다는 점

위 두 상황때문에 유니온파인드가 생각났으며, O(MlgN)의 복잡도로 코드를 짜는데 성공하였다.

마지막에 i==find(i) 부분이 인상깊었다. 

find(i)!=find(j) 와 같이 코드를 짜려다가, 도저히 원하는 결괏값이 안나와 고민하던 중,

자신이 다른 부모에 엮여있을 경우, 선택권이 없다는 점을 이용해 i==find(i)일 경우 답에 2를 곱해주는 방식을 이용하였다.

 

출처를 보아하니 제1회 소프트콘 이라 하는데, 다른 문제들은 상당히 어려워보이므로

좋은 문제셋들을 풀 수 있는 실력을 갖추기 위해 열심히 ps해야할 듯하다 :)

---

C. 나의 인생에는 수학과 함께

www.acmicpc.net/problem/17265

17265번: 나의 인생에는 수학과 함께

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 6;
const int INF = 1e9 + 7;
int N, ans1 = -INF, ans2 = INF;
char a[MAX][MAX];
int dx[2] = { 0,1 };
int dy[2] = { 1,0 };
void bfs(int x, int y) {
	queue<pair<pair<int, char>, pair<int, int>>> q;
	q.push({ {a[y][x] - '0', '+'}, {x, y} });
	while (!q.empty()) {
		int n = q.front().first.first;
		char ch = q.front().first.second;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();
		if (y == N - 1 && x == N - 1) {
			ans1 = max(ans1, n);
			ans2 = min(ans2, n);
		}
		for (int i = 0; i < 2; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				if (a[ny][nx] == '+') {
					q.push({ {n, '+'}, {nx, ny} });
				}
				else if (a[ny][nx] == '-') {
					q.push({ {n, '-'}, {nx, ny} });
				}
				else if (a[ny][nx] == '*') {
					q.push({ {n, '*'}, {nx, ny} });
				}
				else {
					if (ch == '+') {
						q.push({ {n+(a[ny][nx]-'0'), ch}, {nx, ny} });
					}
					else if (ch == '-') {
						q.push({ {n - (a[ny][nx] - '0'), ch}, {nx, ny} });
					}
					else if (ch == '*') {
						q.push({ {n * (a[ny][nx] - '0'), ch}, {nx, ny} });
					}
				}
			}
			
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
		}
	}
	bfs(0, 0);
	cout << ans1 << " " << ans2 << "\n";
}

처음에는 dp로 해결해보려 하였다.

사실 dp 탑다운으로 충분히 해결할 수 있을 듯한 문제이다.

 

그런데, 탑다운으로 재귀적으로 짜다보니 연산자 순서가 반대로 적용돼버렸다.

예를 들어 5+5를 한 후 *5를 한 후 +2를 하는 답이 정답이라면,

내 결과는 +2를 한 후 *5를 한 후 +5를 하므로 연산자 순서가 아예 반대로 돼버린 것이다.

 

멘붕이 온 나는 dp에서 해결법을 찾지 못하고,

bfs로 해결법을 바꾸기 시작했다.

그리고 bfs로 접근하면서 인자 순서가 바뀌지 않게 하기 위해 아예 연산결과와 연산자를 queue의 인자에 집어넣기로 하였다. 

 

주의할 점은 최소치를 0으로 하면 WA를 받는다.

이 경우 답이 충분히 음수가 될 수 있으므로 최소치를 -INF로 해주자.

 

쉬우나 은근 구현량이 많아 호흡이 길었던 문제였다...

 

다른 분들 풀이 또한 나와 거의 비슷했다. (queue를 이용한 사람은 거의 없었고, 재귀적으로 접근한 후, 인자로 연산결과와 연산자를 담는다는 점이 많이 비슷했다.)

---

D. 제자리 멀리뛰기

www.acmicpc.net/problem/6209

6209번: 제자리 멀리뛰기

 

문제를 보지도 않았다.

---

E. 크리스마스 트리

www.acmicpc.net/problem/1234

1234번: 크리스마스 트리

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
typedef long long ll;
using namespace std;
const int MAX = 101;
const int INF = 1e9 + 7;
ll N, R, G, B, ans, d[11][MAX][MAX][MAX];
ll df[11];
ll fac(ll n) {
	if (!n)
		return 1;
	return fac(n - 1) * n;
}
ll dp(int lv, int r, int g, int b) {
	ll& ret = d[lv][r][g][b];
	if (ret != -1)
		return ret;
	if (lv == 0) {
		if (r >= 0 && g >= 0 && b >= 0)
			return ret = 1;
		return ret = 0;
	}
	ret = 0;
	if (r >= lv) {
		ret += dp(lv - 1, r - lv, g, b);
	}
	if (g >= lv) {
		ret += dp(lv - 1, r, g - lv, b);
	}
	if (b >= lv) {
		ret += dp(lv - 1, r, g, b - lv);
	}
	if (!(lv % 2)) {
		if (r >= lv/2 && g >= lv/2) {
			ret += dp(lv - 1, r - lv / 2, g - lv / 2, b) * df[lv] / (df[lv / 2] * df[lv / 2]);
		}
		if (r >= lv / 2 && b >= lv / 2) {
			ret += dp(lv - 1, r - lv / 2, g, b - lv / 2) * df[lv] / (df[lv / 2] * df[lv / 2]);
		}
		if (g >= lv / 2 && b >= lv / 2) {
			ret += dp(lv - 1, r, g - lv / 2, b - lv / 2) * df[lv] / (df[lv / 2] * df[lv / 2]);
		}
	}
	if (!(lv % 3)) {
		if (r >= lv / 3 && g >= lv / 3 && b >= lv / 3) {
			ret += dp(lv - 1, r - lv / 3, g - lv / 3, b - lv / 3) * df[lv] / (df[lv / 3] * df[lv / 3] * df[lv / 3]);
		}
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> R >> G >> B;
	memset(d, -1, sizeof(d));
	for (int i = 0; i <= 10; i++) {
		df[i] = fac(i);
	}
	cout << dp(N, R, G, B) << "\n";
}

처음에 아래 예제가 왜 답이 6이 아니고 36인지 고민했다.

3 2 2 2
ans: 36

분명 2 1 1 1의 예제 출력 6에 각 트리에 RGB를 놓는 경우의 수 1을 곱해서 답이 6이 될 듯 한데, 36이라 한 것을 보고 "아, RGB를 섞는 경우의 수까지 생각해야 하는구나" 를 느꼈다.

 

고등학생 때 배운 '같은 순열 섞기' (이거 맞나...?ㅋㅋㅋㅋ) 를 떠올려보자. 

R 2개, G 2개, B 2개를 나열하는 경우의 수는 6!/(2!*2!*2!) 이다.

이걸 이용하는 문제이다.

 

N이 최대 10이므로 10까지 팩토리얼의 값을 df 배열에 저장해놓았다. (dp factorial의 줄임말 ㅎㅎ......)

이후 코드에서 보이는것과 같이 d[lv][r][g][b]=d[lv-1][r`][g`][b`]+ ... (r, g, b의 개수가 충분하면 경우의 수를 더해준다)

의 점화식을 이용하여 풀었다.

 

구현량이 상당히 길지만, 점화식 자체는 복잡하지 않아 왜 골1인지 의문인 문제이다.

난 골3~골2라 생각해 골2에 투표했다.

B번이 더 어려운 듯...

---

후기

개인적으로 B번, C번에서 배울 점이 있었다.

B번은 새로운 유니온파인드 접근 방법을 배운 듯 하다. 

C번은 구현 연습, 그리고 dp 재귀의 이해도를 조금 더 높이는 데 도움이 됐다.

 

아직 내 실력은 애매한 실력인 듯 하다.

ps를 계속 하면 실력이 늘까? 잘 모르겠다. 그렇지만 일단 하는데 까진 해보려 한다.

어떤 코딩테스트에도 겁나지 않을 실력이 됐음 좋겠다.