[BOJ] 제1회 숙명여대 프로그래밍 경진대회 (SMUPC)를 둘러보았다

지난 포스팅에서 언급한 그룹연습을 진행하느라 SMUPC Open Contest에는 참가하지 못했다.

kth990303.tistory.com/48

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

그래서 위 연습이 끝나고 밤에 한 번 숙명여대 SMUPC 문제들을 풀어보았다.

A~E번은 어제 밤에, F~G번은 오늘 업무 끝나고 개인정비시간에 해결해보았다.

www.acmicpc.net/category/detail/2539

제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC)

---

A. 백준 21734. SMUPC의 등장

21734번: SMUPC의 등장

크게 어렵지 않았으나,

'a'~'z'의 아스키코드가 100을 넘어갈 줄 몰랐기 때문에 처음에 풀었을 땐 예제 출력이 제대로 나오지 않았었다.

따라서 n/100 + (n%100)/10 으로 수정을 하여 TC가 제대로 나옴을 확인하고 제출 후 AC를 맞았다.

 

단순히 문자열을 돌면서 그 문자를 int로 변환해준 후, 자릿수의 합만큼 str[i]를 출력해주면 되는 문제였다.

#include <iostream>
#include <string>
using namespace std;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		int n = (int)s[i];
		int cnt = n / 100 + (n % 100) / 10 + n % 10;
		for (int j = 0; j < cnt; j++) {
			cout << s[i];
		}
		cout << "\n";
	}
}

---

B. 백준 21735. 눈덩이 굴리기

21735번: 눈덩이 굴리기

처음에는 dp로 접근하였으나, M이 최대 10이므로 최대 O(2^10)이기 때문에 백트래킹 알고리즘으로 브루트포스 돌렸다.

범위가 N을 넘어갈 때, 그리고 time이 0 미만일 땐 진행하면 안된다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 101;
int N, M, a[MAX], ans;
void solve(int size, int cur, int time) {
	if (cur == N || !time) {
		ans = max(ans, size);
		return;
	}
	if (cur + 1 <= N) {
		solve(size + a[cur + 1], cur + 1, time - 1);
	}
	if (cur + 2 <= N) {
		solve(size / 2 + a[cur + 2], cur + 2, time - 1);
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

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

---

C. 백준 21736. 헌내기는 친구가 필요해

21736번: 헌내기는 친구가 필요해

19학번도 친구가 필요해

기본적인 그래프 탐색 문제이다.

우선 도연이의 위치를 따로 저장하여, 그 위치에서부터 탐색을 시작한다.

bfs를 돌려서 갈 수 있는 곳을 다 탐색하여 'P'를 만나면 answer를 증가시켜준다.

어차피 갈 수 없는 곳에 친구가 있는 경우는 만날 수 없으므로 같은 컴포넌트에서만 탐색하면 된다.

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int MAX = 601;
int N, M, sx, sy, ans;
char a[MAX][MAX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool visit[MAX][MAX];
void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	visit[y][x] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (a[y][x] == 'P')
			ans++;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
				if (!visit[ny][nx] && a[ny][nx] != 'X') {
					visit[ny][nx] = true;
					q.push({ nx, ny });
				}
			}
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			a[i][j] = s[j];
			if (a[i][j] == 'I') {
				sy = i, sx = j;
			}
		}
	}
	bfs(sx, sy);
	if (!ans)
		cout << "TT\n";
	else
		cout << ans << "\n";
}

---

D. 백준 21737. SMUPC 계산기

21737번: SMUPC 계산기

시간 좀 잡아먹으라고 낸 문제인 듯 하다.

그냥 문제에서 말한대로 그대로 구현하면 된다.

다만, 내 코드는 if문 떡칠이라 좋은 코드는 아닌 것 같다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int MAX = 500001;
int N, ans, tmpnum;
string s, tmp;
char ch = '+';
bool flag = false;
void solve() {
	for (int i = 0; i < s.length(); i++) {
		if (s[i] >= '0' && s[i] <= '9') {
			tmp += s[i];
		}
		else {
			if (ch == '+') {
				ans += stoi(tmp);
			}
			else if (ch == '-') {
				ans -= stoi(tmp);
			}
			else if (ch == '*') {
				ans *= stoi(tmp);
			}
			else if (ch == '/') {
				ans /= stoi(tmp);
			}
			tmp = "0";
			if (s[i] == 'P') {
				ch = '+';
			}
			else if (s[i] == 'M') {
				ch = '*';
			}
			else if (s[i] == 'S') {
				ch = '-';
			}
			else if (s[i] == 'U') {
				ch = '/';
			}
			else {
				flag = true;
				ch = '+';
				cout << ans << " ";
			}
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> s;
	solve();
	if (!flag)
		cout << "NO OUTPUT";
}

---

E. 백준 21738. 얼음깨기 펭귄

21738번: 얼음깨기 펭귄

본격적으로 재밌어지기 시작하는 부분이다.

사실 처음에는 문제가 이해가 안됐다.

펭귄은 이동을 안하는건가? 얼음이 깨지는데 펭귄이 깨진다는게 무슨소리지?

이러한 고민을 많이 했고, 실제로 디스크립션이 이해가 힘들어 구글에 '얼음깨기 펭귄 보드게임' 룰을 검색해보았다. 예상 외로 실제로 있는 보드게임이었다. 19학번은 친구가 필요해

 

결국은 얼음과 얼음 사이가 트리 구조로 지지돼있는 형태였고,

펭귄이 있는 얼음이 빨간얼음과 2개 이상의 브랜치로 연결돼 있어야 펭귄이 안떨어지는 거였다.

 

문제에선 최대의 경우의 수를 묻고 있으므로,

펭귄<->빨간얼음 거리가 가장 짧은 2개를 골라주면 된다.

 

난 bfs로 펭귄부터 탐색을 해서, 빨간 얼음을 만나는 순간 cnt를 증가시켰고, 그 때의 거리를 N-1에서 빼주었다.

cnt가 2 이상이 되면 탐색을 종료시킨다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 328001;
int N, S, P, ans, cnt;
vector<int> v[MAX];
bool visit[MAX];
void bfs(int cur, int num) {
	queue<pair<int, int>> q;
	q.push({ cur, num });
	visit[cur] = true;
	while (!q.empty()) {
		int cur = q.front().first;
		int num = q.front().second;
		q.pop();
		if (cur <= S) {
			cnt++;
			ans -= num;
			if (cnt == 2)
				return;
		}
		for (auto i : v[cur]) {
			if (!visit[i]) {
				visit[i] = true;
				q.push({ i, num + 1 });
			}
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> S >> P;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	ans = N - 1;
	bfs(P, 0);
	cout << ans << "\n";
}

순위 밀려나기 전에 한 컷!

코드 실행속도에서 1등 먹은 기념 캡처해보았다. 역시 bfs가 빠르기는 하다.

---

F. 백준 21739. 펭귄 네비게이터

21739번: 펭귄 네비게이터

이 문제부터는 오늘 풀어보기 시작했다.

 

당신은 웰노운을 아는가?를 파악하는 문제..

이 문제부터 좀 어려웠다.

점화식이 잘 생각이 나지 않았다.

조합을 이용하는 것은 분명하고, 현재 얼음보다 오른쪽, 아래에 있는 얼음의 숫자가 더 커야 함은 분명한데 잘 생각이 나지 않았다.

 

그래서 일단 첫째항부터 넷째항까지 나열해보았다. 

1, 2, 5, 14,...

어? 어디서 많이 본 수열 아닌가?

카탈란 수가 생각이 났다. 확신은 안 들었기 때문에 카탈란 수를 염두에 두고 고민해보았는데,

역시 위에 쌍을 다 '('이라 생각하고, 밑에 쌍을 다 ')'이라 생각할 때,

(와 )의 개수가 같아야 하고, 서로 짝이 맞아야 하기 때문에 카탈란 수열을 띄는 것을 확인가능했다!

 

카탈란 수 점화식은 d[i]=d[0]*d[i-1] + ... + d[i]*d[0] 이므로

O(N^2)으로 잘 이용해주면 된다.  

 

카탈란 수는 아래 블로그에서 공부할 수 있다.

예제가 정말 많고 실생활에서 다양하게 쓰인다.

거의 까먹을랑 말랑 했는데 이문제 덕분에 다시 한 번 카탈란 수를 상기시킬 수 있었다. (반대로 생각하면... 카탈란 수 몰랐던 분들은 엄청 어려웠을 듯...)

suhak.tistory.com/77

카탈란 수(catalan number)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX = 10001;
const int MOD = 1e9 + 7;
ll N, d[MAX] = { 1,1,2,5 };
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 4; i <= N; i++) {
		for (int j = 0; j < i; j++) {
			d[i] += d[j] * d[i - j - 1];
			d[i] %= MOD;
		}
	}
	cout << d[N] << "\n";
}

---

G. 백준 21740. 도도의 수학놀이

21740번: 도도의 수학놀이

당신은 웰노운을 아는가?를 파악하는 문제 2..

문자열을 180도 회전하고, 수를 하나 추가하고... 정말 어려운 문제이다.

아니, 어렵다기보단 헷갈린다.

이 문제 또한 문자열을 크게 만드는 정렬 조건이 웰노운이라, 사전지식을 알고 있다면 쉽게 접근할 수 있....는 줄 알았는데 생각보다 어렵다.

www.acmicpc.net/problem/1422

1422번: 숫자의 신

숫자들을 이어붙여서 크게 만들 수 있는 정렬 조건은 아래와 같다.

bool cmp(string s1, string s2){
	return s1+s2>s2+s1;
}

자주 나오니까 알아두도록 하자.

왜 이렇게 되는지 예시를 통해 알아보자.

97, 965 라는 숫자가 있다고 해보자.

더 큰 숫자는 965이고, 길이가 긴 것 또한 965이지만, "97"+"965"의 값인 "97965"가 "965"+"97"의 값인 "96597"보다 크다.

즉, 어차피 문자열과 수의 차이는 '0' 뿐이므로 두 수를 이어붙일 때 s1다음에 s2로 이어붙일지(s1+s2), s2 다음에 s1으로 이어붙일지(s2+s1)의 대소비교는 위와 같이 하면 된다.

예시를 보니 잘 이해가 되는 듯 하다. 

 

문제는, 이 조건을 알고 있어도 180도를 회전한다는점, 숫자를 하나 추가한다는 점이 굉장히 헷갈린다.

아래 예시를 돌려보자.

4
1 10 100 1000
ans: 10001000100101

만약 수를 180도 회전한 상태에서 가장 큰 수를 찾고 있었다면

"0001", "001", "01", "1" 중에서 큰 수를 찾을 테니 1이 나올 것이다.

 

따라서 한 번 더 집어넣을 숫자는 180도 회전한 상태에서 길이가 가장 길되, 같은 길이일 경우 int형이 더 큰 숫자로 골라야 한다.

그래야 180도 회전한 상태에서 제일 커진다.

 

답을 출력할 때는 180도 회전하기 전 상태에서 출력해야되므로 거꾸로 출력해야 함을 잊지 말자.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100001;
int N;
string tmp, M;
vector<string> v;
bool cmp(string s1, string s2) {
	return s1 + s2 > s2 + s1;
}
bool cmp2(string s1, string s2) {
	if (s1.length() == s2.length())
		return stoi(s1) > stoi(s2);
	return s1.length() > s2.length();
}
void check() {
	reverse(tmp.begin(), tmp.end());
	for (int j = 0; j < tmp.length(); j++) {
		if (tmp[j] == '9')
			tmp[j] = '6';
		else if (tmp[j] == '6')
			tmp[j] = '9';
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		tmp = to_string(n);
		check();
		if (cmp2(tmp, M))
			M = tmp;
		v.push_back(tmp);
	}
	v.push_back(M);
	sort(v.begin(), v.end(), cmp);
	string ans;
	for (int i = 0; i < v.size(); i++) {
		ans += v[i];
	}
	for (int i = ans.size() - 1; i >= 0; i--) {
		if (ans[i] == '6')
			cout << "9";
		else if (ans[i] == '9')
			cout << "6";
		else
			cout << ans[i];
	}
}

---

일단 문제들이 꽤 좋았다.

 

B, C번으로 기초적인 알고리즘을 점검하였고,

D번으로 구현할 줄 아는지 묻고,

E번으로 트리 탐색을 할 줄 아는지 묻고,

F, G번으로 그리디, 카탈란수 등 에듀케이셔널한 웰노운을 소개시켜주는 듯한 문제셋이었다.

 

사실 나도 지금 건국대 백준 대회를 개최하고 싶어 이것저것 문제를 만들어보고 있는 중이라

숙대 문제들에 눈이 가지 않을 수가 없었다.

숙대 또한 제1회 대회였었고, 학교 대회인 만큼 성공적인 대회 개최를 맘속으로 작게나마 응원하고 있었기 때문이다.

부러운 점은 후원이 많다는점? 검수비 10만원을 지불할 정도의 후원이 너무 부러웠다...

9월에 개최할 건국대 대회는 후원이 들어올지조차 모르겠다.

 

생각보다 난이도가 높아 E, F, G번은 교내에 정답자가 아무도 없는 것으로 알고 있다.

의도한건지, 예상보다 난이도가 높아진건지는 모르겠다.

확실히 출제자와 참여자 입장은 많이 다르다는 것을 이번 대회 결과에서도 깨닫게 된다.

 

나도 지금 따로 문제를 만들고 있다 보니 출제, 테스트케이스 구성, 디스크립션 제작이 얼마나 힘든지 새삼 느끼는 중이다. (사실 그렇다보니 smupc 문제들이 지금 내가 만들어놓은 초안과 겹치는지 여부를 제일 먼저 파악해봤다ㅋㅋㅋ 겹치면 내꺼 갈아엎어야돼서...)

출제진들과 검수진들이 노력한 흔적이 보이는 좋은 문제셋인듯 하다.