본격적으로 PS공부를 하기로 하고, 첫 CP여서인지 어려웠다.
대회 당시에 A, B, C 문제는 쉽게 풀었다. A는 솔브닥 기준으로 브론즈 5 수준의 쉬운 문제였고, B도 브론즈 1 정도의 난이도였다. C는 문제를 처음엔 잘 이해하지 못했지만, 나이브하게 풀어도 풀렸다. 체감 난이도로는 실버 중위권 정도인 것 같다.
> A 소스
#include <stdio.h>
int main()
{
int a, b;
scanf("%d %d", &a, &b);
if(a == 1 && b == 0) printf("Yes");
else if(a == 0 && b == 1) printf("No");
else printf("Invalid");
return 0;
}> B 소스
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
int arr[110][110];
int main()
{
int i, j;
scanf("%d", &n);
for(i=1;i<=n;i++) {
for(j=1;j<=i;j++) {
scanf("%d", &arr[i][j]);
}
}
int res = 1;
for(i=1;i<=n;i++) {
int x = max(res, i), y = min(res, i);
res = arr[x][y];
}
printf("%d", res);
return 0;
}> C 소스
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<string> vec;
int main()
{
int i, j;
string s1, s2;
cin >> s1 >> s2;
string x = s1;
for(i=0;i<s1.size();i++) {
if(s1[i] != s2[i]) {
if(s1[i] > s2[i]) {
x[i] = s2[i];
vec.push_back(x);
}
}
}
for(i=s1.size()-1;i>=0;i--) {
if(x[i] != s2[i]) {
x[i] = s2[i];
vec.push_back(x);
}
}
printf("%d\n", vec.size());
//sort(vec.begin(), vec.end());
for(i=0;i<vec.size();i++) {
cout << vec[i] << '\n';
}
return 0;
}D에서 막혔는데, 끝나고 나서 에디토리얼을 보니 문제를 잘못 이해하고 있었다. 주어진 좌표가 이미 뚫려 있으면 4방향에서 처음 막힌 곳을 모두 뚫어야 했는데, 나는 가장 가까운 곳만 뚫어야 한다고 착각했다. 그래서 여러 방향이 있을 때만 모두 뚫는 방식으로 풀었다.
정답 풀이 방식은 STL의 set과 이분 탐색을 사용하는 것이었다. 문제를 제대로 이해했다면 어느 정도 근접한 답을 낼 수 있었을 텐데, 아쉬웠다.
(09-08) 일어나자마자 D 문제까지 업솔빙을 마쳤다. 아직 STL에 익숙하지 않아서인지, set을 잘 활용해보지 않아서인지 처음 보는 함수들이 있었고, 포인터 형식이나 람다 함수처럼 평소에 쓰지 않던 개념들이 많아 신기했다. 그래도 이해는 갔다. 앞으로 set이나 vector 같은 자료구조를 사용할 때는 iterator를 더 적극적으로 사용해야겠다.
> D 소스
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;
int main()
{
int i, j;
int H, W, Q;
cin >> H >> W >> Q;
vector<set<int>> g1(H), g2(W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
g1[i].insert(j);
g2[j].insert(i);
}
}
while (Q--) {
int x, y;
cin >> x >> y;
x--;
y--;
if(g1[x].count(y)) {
g1[x].erase(y);
g2[y].erase(x);
continue;
}
//위
auto it = g2[y].lower_bound(x);
if(it != g2[y].begin()) {
g1[*prev(it)].erase(y);
g2[y].erase(*prev(it));
}
//아래
it = g2[y].lower_bound(x);
if(it != g2[y].end()) {
g1[*it].erase(y);
g2[y].erase(*it);
}
//왼쪽
it = g1[x].lower_bound(y);
if(it != g1[x].begin()) {
g2[*prev(it)].erase(x);
g1[x].erase(*prev(it));
}
//오른쪽
it = g1[x].lower_bound(y);
if(it != g1[x].end()) {
g2[*it].erase(x);
g1[x].erase(*it);
}
}
int ans = 0;
for(i=0;i<H;i++) ans += g1[i].size();
cout << ans << '\n';
return 0;
}
결론
앞으로 앳코더 같은 플랫폼에서 더 자주 CP(Competitive Programming)를 해봐야겠다고 생각했다. 앳코더 민트 랭크에 도전해보고 싶어서 열심히 준비할 계획이다. 코드포스는 대회 시간이 너무 늦어 참여할 수 있을지 모르겠지만, 어쨌든 최근 내 실력을 돌아보며 자괴감이 들어서, 한동안 알고리즘 공부에 더 집중해야겠다고 결심했다.