티스토리 뷰
나는 처음 1시간 동안 문제를 읽고 생각한 뒤, 예상 난이도를 결정하고 문제를 풀기 시작하는 스타일인데 문제를 본 결과 1번은 풀 수 있어 보였고, 2번도 잘 생각하면 풀 수 있어 보였지만, 3번은 잘 생각이 나지 않았다.
그래서 1번을 푼 뒤 2번을 생각하고, 3번은 마지막에 긁기로 했다.
1번은 난이도 순서대로 정렬되어 있는 책 N개 중 K개를 골라서 책의 난이도 합이 A 이상 2A 이하가 되도록 해야 하는 문제인데, 책의 난이도는 S번만 볼 수 있다. 경우의 수는 NCK개가 있었는데, 이를 다 볼 수는 없으므로 2가지로 나누어서 풀었다.
1.가장 작은 거 K-1개와 합쳤을 때 A 이상이 되는 가장 작은 책 하나를 골라, K개를 만든다.
2.1번에 해당되는 책이 없을 경우, 가장 작은 거 K-1개와 합쳤을 때 A 미만인 것 중 가장 큰 것과 그것 왼쪽에 있는 K개들을 고른 뒤, 완전 탐색으로 22K-1 가지를 모두 본다. K가 10 이하이므로 시간 복잡도는 충분하다.
처음 볼 때는 이 두 가지 경우를 생각 못하고 A/K 이상인 가장 작은 원소 주변만 보면 충분하다고 생각해서, 45점을 맞았다.
그 뒤 케이스를 다신 분석해 보니 1번 케이스를 찾을 수 있었고, 쿼리 횟수가 너무 많아서 A/K 이상인 원소를 찾는 쿼리를 줄일 방법을 생각하다가, A 미만이 되는 가장 큰 원소 근처는 답이 될 가능성이 있어 보인다고 생각했고, 가장 작은 거 K-1개도 구해져 있기 때문에 이를 활용해서 2번 케이스를 만들었다.
쿼리 개수는 logN(A 이상인 가장 작은 책 찾기)+K-1(가장 작은 거 K-1개 알기)+K(A 미만인 가장 큰 책 주변 알기)이다.
2번은 서버 N개에 서로 다른 데이터가 있는데, 서버 두 개가 데이터를 N-1번 공유하여 공유한 서버 정점 두 개를 이어 만든 그래프는 트리를 이루고, 중간중간에 어떤 서버가 어떤 데이터를보자마자 비트셋으로 뚫으면 만점을 받을 수 있다는 생각이 들었다. 하지만 생각해 보니 비트셋으로는 원소의 개수 쿼리를 처리하기 어렵다는 것을 알았다. 그래가지고 x축이 데이터, y축이 서버이고, (x,y)는 y서버가 x데이터를 가지고 있는 좌표평면이 있을 때, 비트들을 8*8 정사각형 형식으로 쌓은 뒤 업데이트와 쿼리를 비트 연산과 popcount로 해서 시간 복잡도를 1/8 하는 방법과, 이를 심드로 최적화해서 16*16 정사각형을 만드는 방식 들을 생각했으나, 충분히 시간 복잡도가 줄어들지 않아 버렸고, 비트셋으로 52.5점을 먼저 긁었다.
그 뒤에는 이를 바탕으로 특정 형식에 그래프에서 어떻게 할 수 있을지를 생각했다. 트리라는 조건이 필요 없는 비트셋을 생각하다 보니 트리에 대해서 어떻게 적용해야 할지는 잘 감이 오지 않았다.
3번을 봤다. 그래프에 K명의 감시관이 특정 경로를 무한히 반복하며 돌아다니는데, 이들과 정점이나 간선에서 만나지 않고 1번 정점에서 N번 정점으로 가야 했다. 감시관의 경로들이 겹치지 않는다는 조건이 있었고 이게 풀이에 중요해 보였는데, 이를 어떻게 풀이에 사용할지 전혀 알 수 없었다. BCC 등을 생각해 봤으나 전혀 감이 오지 않았다. 그래서 유일하게 (정점, 시간)을 정점으로 하는 BFS로 풀 수 있었던 5점 섭테를 긁고, 이를 확장해서 내가 보기에도 말이 안 되는 15점 풀이를 내 봤으나 당연히 틀렸다.
이후로는 2번의 스타 그래프인 케이스가 쉬워 보여서 했는데, 너무 쉽다고 판단한 나머지 테스트도 거의 하지 않았고, 결국 아홉 번 정도나 제출을 하여 풀게 되었다.
이번 셋에서 느낀 점은 한 접근을 너무 오래 붙잡고 있을 경우 다른 접근에 관련된 섭테를 생각하기 어렵다는 것이다. 앞으로는 이 점을 유의하고, 여러 접근에 대해 조금씩은 생각해봐야 할 것 같다.