[210320] SCOFE 스코페 2021 1차대회 후기

오늘 경험 삼아 실제 첫 코딩 대회를 치러봤다.

문제를 포스팅해도 될지 모르겠어서, 대회가 끝난 후 내가 작성한 코드만 포스팅해보고, 스코페 1차 후기 느낀 점 및 개인적인 난이도를 기록해보려고 한다.

 

 

대회 도중 14:30 ~ 15:30 총 한 시간 가량, 제출에 실패했다는 문구가 계속 떴다.

문의팀에서도 16시경, 해결방안을 아예 모두에게 공지했으며, 나만 문제가 발생한 게 아닌, 응시자 모두에게 문제가 발생한 것으로 보아 서버가 터진 듯하다.

 

5번 문제 '시선 이동' 문제는 정답 처리를 받은 이후, 다시 메모리를 조금 아끼려고 수정 후 재제출했는데, 설마 제출 시각이 늦어져서 오히려 더 불리하게 작용되는 것은 아닐지 불안불안... 하다.

 

대회 자체가 크게 어렵지 않기도 했지만, 어쨌든 첫 대회였으므로 All Solved를 기록해서 기분이 꽤 괜찮았다. 맞왜틀... 을 좀 줄일 필요가 있겠다.

 

-- 2차 대회 후기는 아래 포스팅에서 볼 수 있습니다!

https://kth990303.tistory.com/20

[210327] SCOFE 스코페 2021 2차대회 후기

---

문제 정보

문제 이름	Solved.ac 난이도	사용 알고리즘
대여 시간을 추천해드립니다	Bronze II	문자열, 정렬
배송 전략 실험	Silver IV	DP
상품 배치 추천	Silver IV	브루트포스
안 본 컨텐츠 없게 해주세요	Bronze I	정렬
시선 이동	Silver II	BFS
팝업스토어	Silver II	DP

solved.ac 난이도는 제 주관이 들어갔습니다.

---

1. 대여 시간을 추천해드립니다

사용 알고리즘: 문자열, 정렬

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 21;
int N, a[MAX];
vector<string> v1, v2;
bool cmp(string s1, string s2) {
	return s1 > s2;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	v1.resize(N); v2.resize(N);
	for (int i = 0; i < N; i++) {
		string s;
		cin >> v1[i] >> s >> v2[i];
	}
	sort(v1.begin(), v1.end(), cmp);
	sort(v2.begin(), v2.end());
	if (v1[0] > v2[0]) {
		cout << -1 << "\n";
		return 0;
	}
	cout << v1[0] << " ~ " << v2[0] << "\n";
}

그냥 무난 무난한 정렬 문제였다.

문자열이 14:00 ~ 19:00 이런 식으로 주어져서, getline으로 받고 ':' 표시 삭제하고 '~'표시 처리하는 등등 엄청난 삽질을 했었는데, 생각해보니까 시간과 시간 사이 공백이 있어서 그냥 cin으로 받으면 되는 문제였다.

 

지금 생각해보면 삽질했음에도 불구하고 9분 만에 풀어 정말 다행이라고 생각된다.

이거랑 비슷하지만, 좀 어려운 백준 문제가 있는데 바로 아래 문제이다.

www.acmicpc.net/problem/16496

16496번: 큰 수 만들기

카카오 프로그래머스에도 있는 문제이니 한번 풀어보면 좋을 듯하다.

---

2. 배송 전략 실험

사용 알고리즘: DP

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 51;
ll N, d[MAX];
string s;
ll dp(ll cur) {
	ll& ret = d[cur];
	if (cur == N - 1)
		return ret = 1;
	if (cur >= N)
		return ret = 0;
	if (ret != -1)
		return ret;
	ret = 0;
	if (cur + 1 < N && s[cur + 1] == '1')
		ret += dp(cur + 1);
	if (cur + 2 < N && s[cur + 2] == '1')
		ret += dp(cur + 2);
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> s;
	fill(d, d + MAX, -1);
	cout << dp(0) << "\n";
}

long long형으로 처리해주지 않아 14시 17분경, WA를 받았다. 14:27에 AC를 받았는데, 최대치 테스트 케이스를 잘 잡아내는게 진짜 중요한 것 같다.

 

long long형으로 해주지 않으면 아래와 같은 테스트케이스를 통과하지 못한다.

50
11111111111111111111111111111111111111111111111111
ans: 12586269025

앞으로는 바로바로 최대치부터 잘 집어넣어보는 연습을 해야겠다. 아마 대부분 long long 때문에 까이지 않을까 싶다. 나도 이 부분 때문에 10분을 날렸다.

---

3. 상품 배치 추천

사용 알고리즘: DP, 브루트 포스 (정해는 단순 브루트 포스일 듯)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 51;
int N, a[MAX][MAX], d[MAX][MAX], res, M;
vector<int> ans;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			a[i][j] = s[j] - '0';
			if (a[i][j]) {
				d[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (a[i][j]) {
				if (i>0 && j>0 && d[i - 1][j] && d[i][j - 1] && d[i - 1][j - 1]) {
					d[i][j] = min({ d[i - 1][j], d[i][j - 1], d[i - 1][j - 1] }) + 1;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			M = max(M, d[i][j]);
		}
	}
	ans.resize(M + 1);
	for (int k = 1; k <= M; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (d[i][j] >= k) {
					ans[k]++;
				}
			}
		}
	}
	
	for (int i = 0; i < ans.size(); i++) {
		res += ans[i];
	}
	cout << "total: " << res << "\n";
	for (int i = 1; i <= M; i++) {
		cout << "size[" << i << "]: " << ans[i] << "\n";
	}
}

이 문제를 풀고 14:45분경에 제출할 때쯤에 서버가 터졌었다.

참고로 이 문제는 아래 백준 문제와 상당히 유사하다.

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

그룹 연습 Div.1에서 진행한 문제.

 

다만, 스코페 문제가 N 범위가 더 작아 dp를 사용하지 않고도 AC를 받을 수 있을 듯한데,

나는 dp 풀이가 코드가 간결하고 편해 dp풀이로 하였다.

 

이 문제 또한 맞왜틀하기 좋은 문제다.

dp 부분을 처리할 때, d[i-1][j], d [i][j-1], d[i-1][j-1] 이 부분에서 i=0, j=0일 때 음수 index를 참조하기 때문에 런타임에러가 뜬다. 나도 이 점 때문에 맞왜틀을 찾는 데에 매우 헤맸었다. 

비쥬얼스튜디오는 이 부분을 알아서 잘 처리해주기 때문에 비쥬얼스튜디오에선 잘 돌아가지만 말이다...

 

세그먼트 트리를 제외한 웬만한 경우에서 1부터가 아닌 0부터 시작하는 내 습관이 여기서는 큰 독이 된 것이다. (그래도 바꿀 생각은 없다.)

 

if문 조건 설정 시, 항상 범위 체크 잘하자! 

---

4. 안 본 컨텐츠 없게 해주세요

사용 알고리즘: 정렬

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 101;
int N, M;
char visit[MAX][MAX], info[MAX][MAX];
double a[5];
typedef pair<pair<char, double>, pair<int, int>> pi;
vector<pi> v1, v2;
bool cmp(pi p1, pi p2) {
	if (p1.first.second == p2.first.second) {
		if (p1.second.first == p2.second.first)
			return p1.second.second < p2.second.second;
		return p1.second.first < p2.second.first;
	}
	return p1.first.second > p2.first.second;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cout << fixed;
	cout.precision(1);

	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			visit[i][j] = s[j];
		}
	}
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			info[i][j] = s[j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visit[i][j] == 'Y')
				v1.push_back({ {info[i][j], a[info[i][j] - 'A']},
					{i, j} });
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visit[i][j] == 'O')
				v2.push_back({ {info[i][j], a[info[i][j] - 'A']},
					{i, j} });
		}
	}
	sort(v1.begin(), v1.end(), cmp);
	sort(v2.begin(), v2.end(), cmp);
	for (int i = 0; i < v1.size(); i++) {
		cout << v1[i].first.first << " " << v1[i].first.second << " "
			<< v1[i].second.first << " " << v1[i].second.second << "\n";
	}
	for (int i = 0; i < v2.size(); i++) {
		cout << v2[i].first.first << " " << v2[i].first.second << " "
			<< v2[i].second.first << " " << v2[i].second.second << "\n";
	}
}

왜 4번에 이렇게 쉬운 문제가 있지? 싶었던 문제. 

근데, 코드 작성해보니까 왜 4번인지 알 것 같았다.

노가다...

 

간결한 풀이가 더 존재할진 모르겠어도,

다른 문제에 비해 조금 더 노가다성이 있는 건 확실하다. 왜냐, 입력받을 정보가 좀 많기 때문이지~

 

그냥 정렬 조건 설정할 줄 알면 잘 풀린다.

 

근데 난 이것도 WA를 받았었다 (진짜 빡대가린가?)

정렬 순서 정할 때, 설정 기준을 따로 정해두지 않으면, 컴파일러가 첫째 항부터 오름차순으로 자동 정렬하는데,

난 이 부분을 고려하지 않고 선호도 기준으로만 정렬하면, 위치도 알아서 정렬될거라 생각해

선호도 기준으로만 정렬했다. 맨 첫째 항이 ABCDE 장르 종류라 이 부분이 정렬되는 건 잊고...ㅋㅋㅋㅋㅋㅋ

---

5. 시선 이동

사용 알고리즘: BFS

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstring>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 1001;
const int INF = 1e9 + 7;
int N, M, ans = INF;
int dx[3] = { 0,-1,1 };
int dy[3] = { 1,0,0 };
char a[MAX][MAX];
bool visit[MAX][MAX];
int bfs(int x, int y) {
	queue<pair<int, pair<int, int>>> q;
	q.push({ 0, {x, y} });
	visit[y][x] = true;
	while (!q.empty()) {
		int cnt = q.front().first;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();
		if (y == M - 1)
			return cnt;
		for (int i = 0; i < 3; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
				if (!visit[ny][nx] && (a[ny][nx]=='.'|| a[ny][nx]=='c')) {
					visit[ny][nx] = true;
					if (!i)
						q.push({ cnt, {nx, ny} });
					else
						q.push({ cnt + 1, {nx, ny} });
				}
			}
		}
	}
	return -1;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); j++) {
			a[i][j] = s[j];
		}
	}
	for (int j = 0; j < N; j++) {
		memset(visit, false, sizeof(visit));
		if (a[0][j] == 'c')
			ans = min(ans, bfs(j, 0));
	}
	cout << ans << "\n";
}

이 문제부터 배점이 20점이 아닌, 30점이었다.

 

이 문제도 맞왜틀을 겪었는데, 'c' 또한 '.'과 같이 이동할 수 있는 경로로 설정해줬어야 했다.

이동할 수 없는 경우 -1 처리도 잘 해주었고, bfs는 내가 제일 자신있어하는 파트인데 WA를 받으니까 너무 답답했었다.

설마 a[ny][nx]=='c' 처리를 if문으로 안해줘서? 라는 생각이 들어서 작성했고, 다행히 AC를 받았다.

 

이 문제 또한 백준에 비슷한 문제가 있다.

www.acmicpc.net/problem/13565

13565번: 침투

그룹 연습Div.2 에서 진행한 문제.

 

그리고 스코페 특이한 점.

가로, 세로 입력받을 때, 백준에서는 세로, 가로 N, M 이렇게 입력받는데,

스코페는 가로, 세로 N, M 이렇게 입력받는다.

이 점 때문에 백준이나 프로그래머스 등 ps에 익숙한 사람들은 주의해야 한다.

 

3번문제부터, 이 문제 풀 때까지 '제출에 실패하였습니다' (대회 측 서버가 터짐) 가 떠서 진짜 머릿속에 온갖 생각이 다 들었지만,

이런 거 하나하나에 신경쓰다가 다른 문제 못 풀기 때문에 미련을 버리고 6번을 풀러갔다.

---

6. 팝업스토어

사용 알고리즘: DP

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
typedef long long ll;
#define all(v) v.begin(), v.end()
using namespace std;
const int MAX = 10001;
ll N, M, d[MAX][101], a[MAX][101];
ll dp(int x, int y) {
	ll& ret = d[y][x];
	if (y >= N || x >= M)
		return ret = 0;
	if (ret != -1)
		return ret;
	ret = 0;
	if (y + 1 < N) {
		ret = max(ret, dp(x, y + 1));
	}
	if (x + 1 < M) {
		ret = max(ret, dp(x + 1, y));
	}
	return ret += a[y][x];
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a[i][j];
		}
	}
	memset(d, -1, sizeof(d));
	cout << dp(0, 0) << "\n";
}

배점 30점짜리 문제이나, 크게 어렵지 않은 dp문제이다.

2번 문제가 생각나, 이 문제는 아예 처음부터 long long형으로 처리했다.

다행히 원트로 맞았고, 이 문제 제출하고 나서, '제출에 실패하였습니다' 현상이 해결돼, 다른 문제(3~5번)도 제출하러 갔다. (그리고 3,4,5번 모두 맞왜틀을 당했다)

---

후기

일단 내 진행상황은 대략 아래와 같았다.

---

14:00 대회 시작

14:09 1번 AC

14:17 2번 WA

14:27 2번 AC

14:30 ~ 15:50 서버 터짐 (문제 구경 및 테스트케이스 실행은 가능)

3,4,5번 각각 20분 씩 걸린 듯 하다.

15:58 6번 AC

15:59 3번 WA

15:59 4번 WA

15:59 5번 WA

16:08 3번 AC

16:24 5번 AC

16:36 4번 AC

16:37 5번 AC (메모리 조금 더 최적화)

16:40 시험 종료

18:00 대회 종료

---

좀 더 시간을 줄이는 연습을 많이 해야겠다.

난 어려운 문제를 시간을 오래 가지고 고민해보는 걸 좋아하는 편이다.

그래서 그런지, 시간에 쫓기는 경험을 싫어하다보니 하지 않으려하는 경향이 강하다. 그래서 백준 그룹연습 스터디를 만든 것이고. 

앞으로 이러한 연습을 싫다고 피하지 않고, 더욱 더 열심히 참여해서 시간관리를 잘 할 수 있는 나만의 노하우를 만들어야겠다.

 

이번 문제들이 난이도가 비교적 높지 않아 올솔이 가능했지만, 

• 1. 백준 플레티넘 티어임에도 불구하고, 이러한 문제를 푸는데 걸린 시간이 오래 걸림.
• 2. 더 어려운 문제가 나왔다면 과연 나는 잘 풀 수 있었을까

이러한 생각이 많이 들게 해 준 대회였다.

겸손해지고 연습에 정진해야겠다.

 

뭔가 후기에 더 적고싶은데, 생각이 안난다. 생각나면 더 적어봐야겠다.

 

---

(21.03.23. 추가)

한 60% 정도의 확률로 합격하지 않을까 예상했는데, 다행히 합격했다는 소식이 문자와 메일로 왔다.

 

1차 대회 중, 1,000명을 합격시켜 2차로 보낸다고 하였고, 

다행히 천 명 안에 들은 듯하다.

이곳저곳 후기를 들어보니 5솔까지 합격한 듯 하다.

합격 메일에 모의테스트 안내와 캠 사용 필수, 그리고 채점 기준이 나와있었는데,

최대한 제출시간을 빠르게 하는 것이 관건이었다.

2차 대회때는 메모리 최적화, 시간제한이고 뭐고,

일단 조건에 맞는 시간복잡도 풀이라 생각되면 빠르게 제출하도록 해야겠다.

 

2차 대회는 좀 더 어렵지 않을까 예상된다.

2차 대회에 진출한 것만으로도 기쁘고, 첫 대회인만큼 경험이 중요하다고 생각하기 때문에 어서 2차 대회 때 더 어려운 문제들을 구경하고 싶다. 

 

2차 대회 후기는 아래 포스팅에서 볼 수 있습니다!

https://kth990303.tistory.com/20

[210327] SCOFE 스코페 2021 2차대회 후기