[220220] ICPC Sinchon Winter Algorithm Camp Contest Open 후기

오랜만에 BOJ 대회에 참여해보았다!

신촌 지역 연합대학들은 ps/알고리즘 스터디들 서로 진행하고 매 해 겨울, 여름마다 대회를 연다.

나는 신촌 연합대학에 속하지 않기 때문에 open contest 참여자로 응시해보았다.

 

요즘 우테코를 하느라 백준을 많이 못해서 내 감이 얼마나 잘 유지되고 있는지 중간체크도 할 겸,

대회시작 40분 쯤 후부터 뒤늦게 참여해보았다.

9등의 좋은 성적을 기록했다.

꽤 만족스러운 결과였다 :)

 

물론, 등수가 높다고 꼭 잘하는건 아니긴 하지만,

풀 만한 문제들은 만족스럽게 잘 푼 듯하다.

---

참여 후기 / 느낀점

• 수학적인 능력을 많이 요구하는 느낌이었다. 운영진분들께서 다들 수학을 잘하시다보니 ㅎㅎ
• 초보자 입장에선 꽤 헤맬 듯한 문제들이 많았다고 생각한다. C번부터 초보자에게는 굉장히 어려웠을 것 같다고 생각. (이후에 티어가 S3 정도로 나와있던데, 나는 S2 정도라 생각한다.)
• E번 구현 문제가 꽤 재밌었다. 난 중간에 삽질하긴 했지만... 그래도 다행히 한번에 맞았다 ㅎㅎ 현실에서도 C 전염병이 치료제가 있는 쪽엔 안 퍼지면 좋겠다... 그리고 H번은 보고 감탄했다. 쉽지만 쉽지 않은 문제. 코포 스타일 문제들과 닮았는데, 그 중에서도 되게 좋다고 생각되는 문제이다.
• 중간에 잠깐 삽질한 거 빼고, 실력발휘 괜찮게 잘 한 느낌? 맞왜틀을 많이 외친 문제가 거의 없었다! 예전엔 무지성 맞왜틀 많이 외쳤었는데, 나름 발전한듯 :)

 

각 문제 별 느낀점, 후기는 아래에 작성하도록 하겠다.

---

A - 시간복잡도를 배운 도도

 

테스트 케이스가 적고, 문자열 길이도 10,000을 넘지 않기 때문에 for문으로 비교해주면 된다.

주의할 점은, 문자열 범위를 넘어나는 구간을 체크하지 않도록 해주어야 된다.

 

이렇게 문자열을 반복문으로 탐색하면 간단하게 AC를 받는다.

몸풀기용 문제로 적당한 난이도이지만, 예외처리 안하면 틀릴 수도 있을 듯.

---

B - 상품의 주인은?

이차원 배열을 입력받고, 탐색은 행렬을 바꾸어서 열->행 순서로 진행해야 되는 구현 문제.

초보자 입장에선 인덱스를 바꿔 진행해야돼서 헷갈렸을 것 같다.

 

다른 참여자들 난이도 기여를 보니까 정렬로도 풀 수 있다고 한다.

현재 티어는 S5이다.

---

C - queuestack

조금 어려워지기 시작하는 구간.

처음에 문제 이해가 잘 안됐는데, 스택이면 어차피 입력으로 넣은 값이 반환되고, 큐면 원래 있던 값이 반환된다는 점을 이용해서 매 원소 삽입 때마다 O(1)에 해결할 수 있다.

 

난 Ai 자료구조가 큐인 i들을 따로 저장해두어, 이 때 넣은 값들과 입력으로 들어온 값들을 큐에 넣어주는 방식으로 진행하였다.

이 문제도 초보자들한테 어려웠을 것 같아서 S2에 투표하였다.

---

D - Bottleneck Travelling Salesman Problem (Small)

단순한 브루트포스 백트래킹 문제인데,

괜히 예전에 풀었던 문제가 생각이 나서 플로이드 와샬 -> 백트래킹으로 뇌절쳤던 문제이다.

 

이 문제는 경로를 출력해야 되기 때문에, 플로이드와샬을 쓰면 안되는데다가, 

플로이드와샬을 쓰면 한번씩 방문해야된다는 방문체크를 못하기 때문에 고민 후, 플로이드 코드를 빼고 AC를 받았다.

---

E - 좀비 바이러스

현재 코로나가 심각한 상황을 오마주해서 만들어진 문항으로 추측된다.

꽤 재밌었는데, 동시에 전염되면 3번 바이러스로 바뀌기 때문에 방문체크 배열을 시간을 저장하는 배열로 바꿔서 진행하였다.

 

queue에 넣는 정보가 꽤 많았는데, x좌표, y좌표, 바이러스정보, 바이러스전염시각 총 4개의 정보를 넣어서 진행해주었다.

 

삼성 코테 구현량보다 약간 적으면서도 삼성코테에 어울리는 느낌?

---

F - n번째 숫자 찾기

꽤 어려운 문제라 생각된다. 

N이 2e9까지의 범위이기 때문에 이분탐색을 이용하거나, 수학적으로 구현하는 방식으로 시간복잡도를 줄여야 하는데,

결국 둘 다 비슷한 논리이긴 하다.

 

k의 자리 수, k+1의 자리 수, ... 가 존재할 때, 각 자리 수에 따라 N번째 숫자가 어디에 존재하는지 등차수열 합 공식을 통해 (또는 이분탐색) 찾아야 한다.

문제는 이게 YJ number 정의에서의 범위에서 찾는 것이기 때문에, X number에서 몇 번째 숫자인지도 찾아야 된다. 

여기서 나는 먼저 범위를 비슷한 방법으로 찾아주어 범위를 좁혀 시간복잡도를 줄이고,

진법변환을 이용해주면서 string을 붙이는 방식으로 했는데, string 자체가 시간이 오래 걸리는 작업이기 때문에 시간이 꽤 길게 나왔다.

아래에 언급할 I번을 G1~P5 정도로 생각하고,

F번을 P5 정도라 생각하고 있다.

현재 티어는 G1이다.

---

H - 잘 알려진 수열 구하기

정말 재밌고 대단한 문제라 생각된다.

그냥 홀수만 쭉 나열하면 되는데, 홀+홀 = 짝수이며,

K, K-2, K+2, ... 이렇게 있으면 길이가 n일 때, 합은 n의 배수가 되기 때문에 문제 조건을 만족하게 된다.

 

이러한 관찰을 통해 애드혹, 구성적 느낌으로 풀면 되는데,

되게 재밌었고, 이런 문제를 내신 출제자가 정말 대단하게 느껴졌다.

 

도대체 이러한 성질은 어떻게 발견하신걸까...

---

I - 잘 알려진 합 구하기

조화수열과 harmonic_lemma가 생각나는 문제이다.

i가 커질수록 f(i)가 같은 값의 개수는 많아지고, i가 sqrt(N)일 때까지는 같은 값의 개수가 거의 없기 때문에 sqrt(N)까지는 그냥 식 그대로 계산해주고,

sqrt(N)부터 N까지는 같은 값의 개수를 몫과 나머지 성질을 이용해 구해준 후, 

그 범위에서 특정 g(i)가 얼마나 더 쓰이는지 추가로 더해주면 된다.

 

이 때, long long의 범위를 넘어가지 않을까 고민했는데, M이 1e9라고 해도, 그런 경우는 g(i) 나머지가 같은 개수가 없기 때문에 범위를 벗어날 걱정을 하지 않아도 됐었다.

조화수열 성질을 응용해서 1~sqrt(N)과 sqrt(N)~N 두 범위로 가르면 되는 문제였지만,

두 스킬 모두 쉽지 않았다고 생각한다.

---

그 외에 https://www.acmicpc.net/problem/24519 (K번) 이 문제도 꽤 많이 풀렸던데, N 범위를 보고 TSP를 이용하겠다는 감은 왔으나, 뭔가 잘 풀리지 않아 다른 문제에 시간을 투자했다.

G번 (히히 못가 문제)은 유니온파인드? 구현? 고민했는데, 다른분들이 많이 풀지 않으셨길래 그냥 바로 패스했다.

(둘 다 아니라고 한다...ㅎㅎ)

 

이렇게 16시까지 대회를 응시했고, 16시 이후엔 개인사정으로 풀지 않았지만, 풀었어도 AC받은 문제 수는 동일했을 것 같다.

---

골드 문제까진 잘 해결하였다 :)

개인적으론 24518번, 24514번이 G1도 괜찮긴 하지만, 플레티넘5에 가도 괜찮다고 생각한다.

 

우테코하면서 시간날 때마다 귀찮다고 골드만 풀지 말고,

조금 더 시간 투자해서 플레티넘도 풀어보는 시간을 가져봐야겠다 :)