한국정보올림피아드(KOI 2021) 2차 시험 후기

총점 : 100/100/0/20=220 (동상, 16.10%, 33위)

 

<세 줄 요약>

1. 뇌절 및 구현장애가 많았던 시험...

2. 코이가 점점 온라인 시험에 적응하고 있다는 생각이 들었음... 감시 & 시스템 철저 bb

3. 문자열 시러 ㅡㅡ

 

1번 문제 - 헬기 착륙장

헬기 착륙장은 1~k의 반지름을 갖는 k개의 동심원으로 이루어져 있으며, 각각의 원은 빨간색 또는 파란색으로 칠해짐.

반지름 i인 원을 칠하는 데에는 정확히 페인트 i통이 필요함.

빨간 페인트 a통, 파란 페인트 b통이 있을 때 만들 수 있는 헬기 착륙장 종류의 수를 출력하시오!

 

1번을 보자마자 아무 생각도 나지 않았다. 그래서 고민하다가 내가 1번도 못 푼다는 사실에 금이 간 멘탈에 대충 테이프를 붙이고 2번으로 향했다. 경험상 아무리 쉬운 문제여도 계속 잡고 있는 것이 능사는 아니었기 때문이다.

 

2번 문제 - 그래프 균형 맞추기

컴포넌트 하나로 이루어진 무방향 연결그래프가 주어짐, 각 간선에는 정수 가중치가 있음.

각 정점에 정수 가중치를 부여해야 하는데, 간선의 양 끝 두 점의 가중치 합은 해당 간선의 가중치와 같아야함.

정수 가중치를 부여할 때에는 부여하는 가중치의 절댓값만큼의 비용이 필요함.

이렇게 가중치를 부여하는 방법이 없으면 No를 출력하고,

방법이 있으면 Yes를 출력한 후 최소 비용으로 부여하는 방법을 출력하시오!

 

2번을 보고 가장 처음에 생각한 기본적인 풀이는 1번 정점에 a라는 가중치를 부여하고, 단순 탐색하여 각 정점에 들어갈 수를 a를 이용하여 표현하는 것이다. 그렇게 하면 각 정점에 들어갈 가중치는 a+k 또는 -a+k로 표현된다. 탐색 중에 충돌이 일어나는 부분이 있으면 No를 출력하거나 a 값을 확정해주는 등 간단한 작업들을 하면 가능 여부를 판단할 수 있었고, 각 정점을 0으로 만든 숫자들을 쭉 나열한 후 중간값을 a 값으로 정해주면 비용이 최소가 된다.

ex) 다섯 개의 정점 가중치 a, a+5, a+1, -a-3, -a+2이면 각 정점을 0으로 만들어주는 -5, -3, -1, 0, 2 중 중간값인 -1을 a 값으로 정해주면 비용이 최소가 된다.

 

사실 풀이를 더 다듬으면 구현이 간단해졌을 수도 있을 것 같은데, 1번을 못 푼 불안감에 싸인 정신 상태는 그걸 생각할 겨를은 없었고, 멘탈 치유도 할 겸 시간이 오래 걸리더라도 천천히 저걸 그대로 구현해보기로 했다. 끝나고 세어보니 무려 42번의 테스트와 8번의 제출 끝에 AC를 받았다. 사실 이 정도로 안했어도 되는데 그냥 나의 정신 상태를 위해 이렇게 풀었다.

 

그러고나서 1번으로 돌아가니 풀이가 바로 보였다. 단순 dp를 사용하는 냅색이었다.

이 문제에 맞게 설명하자면, dp[i][j]를 i개의 동심원을 가지는 헬기 착륙장의 일부를 j만큼의 빨간 페인트로 칠하는 방법의 수로 정의한다. 이렇게 되면 dp[i][j]=dp[i-1][j-i]+dp[i-1][j]로 계산할 수 있다. 하지만 문제에 직접 필요한 것은 구간 합이므로, 각 i별로 누적합 배열을 만들어놓으면 된다. 나는 그 작업을 그대로 dp배열에다가 했고, 그래서 dp[i][j]의 정의는 i개의 동심원을 가지는 헬기 착륙장의 일부를 j통 이하의 빨간 페인트로 칠하는 방법의 수가 되었다.

 

각 tc에 대해서 가능한 헬기 착륙장의 크기 k에 대해 1~k까지 dp배열을 이용하여 가능한 경우의 수를 각각 O(1)에 구해주면 시간복잡도는 O(a*root(2a)+T*root(2a))가 되어 문제를 쉽게 해결할 수 이 문제를 왜 보자마자 못 풀었는지 잘 이해가 되지 않았으나, 그래도 200점은 맞았다는 생각에 안심은 되었다. (필자는 작년 코이에서 뇌절을 하다 0솔 88점이라는 처참한 결과를 낸 경험이 있기 때문에 200점은 꼭 맞자는 생각을 가지고 있었다.)

 

하지만 이미 2시간이 흘러있었다.

 

3번 문제 - 가장 긴 공통 괄호 문자열

 

설마... 했다. 설마... 코이에서 또 문자열을 내겠어... 에이... 제목으로 어그로 끈거 겠지...

 

올바른 괄호 문자열이란, 다음과 같이 정의 된다.

1. ()은 올바른 괄호 문자열이다.

2. X가 올바른 괄호 문자열이면, (X)도 올바른 괄호 문자열이다.

3. X, Y가 올바른 괄호 문자열이면, XY도 올바른 괄호 문자열이다.

4. 올바른 괄호 문자열은 위 세 가지 방법으로부터만 도출된다.

두 괄호 문자열 A, B가 주어진다. A와 B의 공통 부분 문자열 중 가장 긴 올바른 괄호 문자열의 길이를 출력하시오.

 

?????? 진짜 문자열이네? 에이 그래도 문자열 알고리즘은 안쓰겠지~ (결론 : 쓴다고 한다)

일단 3번에 문자열이 박혀있는 거부터 마음에 안 들었다. (1차에서도 3번 문자열 때문에 금상을 날렸기 때문)

풀이를 모르겠다. 그게 전부였다.

4번 섭테가 17점짜리 A=B일 때였는데, 무슨 자신감인지 이 섭테가 가장 긁을 가능성이 높다고 생각했다.

그래서 이 섭테를 열심히 긁기 시작했는데, 풀이가 잘 나오지 않았다. 왼쪽 지점과 오른쪽 지점에 투 포인터를 두고 푸는 방법을 생각해서 구현했으나 틀렸고, 나도 곧 반례를 찾았다. 답이 없다고 생각하여 4번으로 넘어갔다.

 

4번 문제 - 맛집 탐방

N개의 정점으로 이루어진 트리가 주어진다. 트리의 정점에는 M개의 맛집이 있다. 맛집이 없는 정점이나 맛집이 여러 개인 정점도 있을 수 있다. 각 맛집에는 c, d, g라는 3개의 변수가 있다. c는 맛집의 위치, d는 맛집이 배달할 수 있는 거리, g는 맛집의 선호도이다. 이때, 각 간선의 거리는 1이라고 판단한다.

맛집을 원소로 하는 집합들 중에서, 그 어떤 정점에서도 집합 안의 2개 이상의 맛집으로부터 배달을 받을 수 없는 집합들을 생각하자. 즉, 집합 내의 맛집들은 배달 가능 영역이 겹치면 안된다. 이러한 집합들 중에서 원소들의 선호도 합이 최대가 될 때 그 값을 출력하시오!

 

딱 봐도 어려운 문제의 향기가 났다. 그 와중에 탐스러운 섭테가 2개 있었다.

1번 섭테는 9점짜리로 간선이 모두 1-2, 2-3... 으로 이루어진 형태였다. 배달 가능 영역의 끝 지점 기준으로 정렬한 후 간단한 dp를 통해 답을 쉽게 도출할 수 있었다.

2번 섭테는 N<=20, M<=20으로, 2^20이 100만 정도이므로 그냥 나이브하게 풀라는 이야기였다. 비트마스킹이 가능하기 때문에 구현이 크게 어렵지는 않았고, 공짜로 11점을 먹었다.

이렇게 4번에서는 20점만 긁고 미련 없이 떠났다. 내가 더 이상 건드릴 수 없는 문제였고, 주변에 나보다 잘하는 친구들도 대부분 20점만 긁었다. 조금의 관찰을 더해서 트리 dp라는 것은 알아챘지만, 어떻게 dp를 세워야할지 감이 잡히지 않았다. 건너건너 들은 이야기로는 다이나믹 세그와 small to large를 써서 푸는 문제라고 하는데, 난 둘 다 뭔지 모르겠다.

 

그리고 다시 3번 문제로 넘어가서, A=B 섭테를 열심히 긁었으나 또 풀이 오류가 발생했다. 대충 재귀를 이용한 풀이였지만, 코드를 짜는 도중에 반례를 찾아버렸다. 난 O(N)에 될줄 알았는데 알고보니 그 섭테도 세그써서 O(NlogN)까지 데려가야 풀린다더라... 결국 3번을 0점으로 마감하고 말았다.

파라메트릭을 사용하는 가짜 풀이로 데이터가 약한 1, 2번 섭테 18점을 긁은 친구들도 있다. 더 박탈감을 느꼈지만, 가짜 풀이조차 생각 못한 내가 잘못인게 맞다...

 

 

 

220점. 만족스럽지는 않지만 실력대로 나온것 같다. 그럼에도 3번 0점은 아직도 마음에 남는다. 문자열 공부를 더욱 열심히 해야겠다는 생각이 들었다. 전날 친구들과 어떤 유형의 문제가 나올지 대충 예측을 했을 때, 나의 4문제 예측은 (간단한 dp/그래프/기하/어려운 애드혹)이었고, 난이도는 골중-플중-다하-다상 정도를 예측했었다. 트리 dp가 나올 것을 예측한 친구도 있었다. 어쨌든 올림에서 많이 쓰는 스타일도 아닌데다가 1차에서 이미 3번으로 낸 문자열 문제를 또 낼 것이라고 생각하는 사람은 없었고, 먼 별 이후로 이렇다할 문제가 나오지 않은 기하가 하나 이상 나올 것이라는 의견이 많았다. 그래서인지 문자열에 대해 대비가 적었고, 또 당했다. 목표가 은상이었기 때문에 좀 아쉽지만, 이번을 계기로 문자열 알고리즘 정주행을 해야겠다고 느꼈고, 앞으로 더 발전해야겠다고 생각했다.