대회실습 1 (5.7)

<APIO 2012>

문제 난이도가 1->2->3 순서인것 같아서 (사실 1은 유명한 문제라 대충 알고 있었다) 그 순서대로 풀었다.

1. Dispatching

큰 set에 작은 set을 합치는 그 유명한 테크닉을 쓰는 가장 대표적인 문제라고 주변에서 워낙 많이 들었었다. 그래서인지는 몰라도 문제를 직접 읽어 본 적은 없었지만 읽자마자 풀이가 바로 떠올랐고, 짜서 어려움 없이 맞았다.

매니저가 정해지면 그 매니저의 서브트리에 있는 노드들 중 월급이 작은 것부터 최대한 많이 고르는 것이 당연히 이득이다. 따라서 각 서브트리별로 월급 순으로 적절히 정렬된 자료구조를 잘 들고 다닐 수 있으면 될 텐데, 각 노드별로 set을 들고 다니면서 합쳐 주면 편하게 처리할 수 있다.

한 번 고려 대상에서 제외된 노드가 나중에 다시 들어올 일은 없으니 dfs 함수 내에서 각 노드에서 할 일은 자식들의 set을 모두 합쳐준 뒤 월급을 넘지 않는 순간까지 월급이 비싼 노드부터 버려주는 것이 전부다. 여기서 set을 합쳐줄 때 가장 큰 set에다 나머지 작은 set을 합쳐주는 식으로 하면 각 노드가 set을 옮길 때마다 set의 크기가 2배 이상 늘어나므로 옮겨다니는 횟수가 O(logn)이고, 시간복잡도가 O(nlog^2n)이 된다는 것을 쉽게 알 수 있다.

사실 풀이를 안 들었어도 충분히 금방 짤 수 있는 쉬운 문제였던 것 같다.

2. Guard

"닌자가 무조건 있어야 하는 칸"을 다르게 말하면 "그 칸에 닌자가 없으면 절대 조건에 맞게 배치할 수 없는 칸"이 된다. 따라서 각 칸에 대해 "이 칸에 닌자를 넣지 않고 k명의 닌자를 적절히 배치할 수 있는가?"를 빠르게 판단할 수 있으면 된다.

나는 처음에 이 생각까지 한 후 세부 조건을 약간 이상하게 생각해서 한 번 틀린 풀이를 짰다가 조건을 잘못 생각했다는 것을 깨달았다. (코딩이 그렇게 오래 안 걸려서 다행이었다) 그 후 침착하게 다시 세부 조건을 생각해 본 결과, "그 칸에 닌자를 절대 배치할 수 없을 때 조건을 만족시키는 데 필요한 최소 닌자 수가 k보다 커지거나 조건을 절대 만족시킬 수 없을 때"라는 것을 알 수 있었다. (처음에는 "최소 수가 k보다 커지는" 때를 고려하지 않았다)

우선 조건에 의해 닌자가 놓이지 못하는 칸을 적절히 배제하고 나면 (set을 이용하면 편하다) "여러 구간들이 있을 때 최소의 꼬챙이를 사용해 구간들을 모두 꿰똟되, 특정 칸에는 꼬챙이를 꽂을 수 없다"라는 문제를 푸는 것으로 바뀐다. 최소 수의 꼬챙이를 꽂는 것을 deadline first 전략으로 앞/뒤에서부터 해 나간다고 하자. i번째 칸이 닌자가 무조건 있는 칸인지를 판단할 때에는, 앞에서부터 꽃을 때 i번째 칸 왼쪽에 꽂는 가장 오른쪽 꼬챙이와 뒤에서부터 꽂을 때 i번째 칸 오른쪽에 꽂는 가장 왼쪽 꼬챙이를 각각 구했다고 하면, (간단한 전처리와 이분탐색으로 구할 수 있다) i번째 칸에 꼬챙이를 꽂을 수 없으므로 처리되지 않은 구간을 마저 처리하게 위해 꽂아야 하는 꼬챙이의 수는 가운데에 구간이 어떻게 남았느냐에 따라 0개, 1개 또는 2개이다. (segment tree 등을 사용하여 구간에 대한 전처리를 해 놓으면 쉽게 구할 수 있다) 왼쪽, 오른쪽, 중간의 세 부분의 꼬챙이의 수를 합한 값이 k를 넘으면 그 칸은 필수 칸이 된다.

한편, i번째 칸에 닌자가 놓이지 못할 때 조건을 절대 만족시킬 수 없는지 여부는 구간 [i, i]의 존재 여부와 동치이다. 매우 간단히 판별 가능하다.

처음에는 잘못된 풀이를 짜면서, 또 "닌자가 놓이지 못하는 칸을 먼저 배제한다"라는 생각을 못 해 너무 복잡하게 생각하면서 시간을 약간 소모한 것 같다.

3. Kunai

각 쿠나이가 언제 충돌하는지 / 충돌하지 않는지의 여부를 알면 쿠나이가 지나간 영역은 N개의 수평/수직 선분이 되고, 이들이 쓸고 지나간 영역의 넓이이 합은 plane sweeping으로 간단하게 해결할 수 있는 문제로 변한다. 따라서 "충돌 시점"을 효율적으로 계산할 수 있으면 된다.

Naive하게 생각하면 N^2개의 모든 쿠나이 쌍에 대해 충돌할 가능성이 있는지 여부를 먼저 계산한 뒤 시간 순서대로 보면서 각 쿠나이가 실제로 충돌하는 시점을 계산할 수 있다. 이는 O(N^2)으로, 40점을 받을 수 있다.

그런데 사실 실제로 일어나는 충돌의 갯수는 N/2 이하기 때문에, 고려해야 하는 충돌을 잘 선별해 O(N)개 정도의 충돌만 빠르게 골라 낼 수 있다면 좋겠다는 생각을 할 수 있고, 나는 여기까지 생각한 뒤 그 다음을 잘못 생각해 틀린 풀이를 짜고 말았다. (스택을 이용해 충돌이 일어날 수 있는 선상에 있는 쿠나이들을 가까운 것부터 매칭시키는 전략이었는데, 다른 충돌선에 있는 쿠나이가 영향을 미칠 수 있기 때문에 그러면 안 된다)

각각의 충돌선에 대해 적절한 자료 구조를 사용하여 "가장 빨리 충돌하는 두 쿠나이 구하기" 연산과 삭제 연산을 log 정도에 수행할 수 있다면 된다는 생각을 풀이가 잘못된 것을 깨달은 이후 하긴 했지만, 너무 늦어서 (20분 정도 남았던 것 같다) 아쉽게도 더욱 세부적인 생각과 코딩을 하지는 못했다.

40점 풀이를 짜는 데에도 세부 조건을 빼먹어 몇십분 정도를 생으로 날렸다. 침착한 생각이 정말로 중요한 것 같다.

종합 후기

풀이에 접근하는 처음의 아이디어를 잘 생각해 놓고 그 다음 세부적인 생각에서 삐끗한 뒤 그것을 알아차리지 못하고 틀린 풀이를 짜다가 나중에 깨닫고 시간 낭비를 하는 경향이 많은 것 같다. OI는 시간 페널티가 없는 대회인 만큼 성급하게 키보드에 손부터 나가지 말고 생각을 침착하게 하고, 내 풀이가 맞는지 여러 번 중간에 검토해 보는 습관을 길러야겠다. 특히 나는 대회를 하면 긴장을 하다 보니 "이러면 되겠다"라는 생각이 약간 들면 세부 조건에 대한 생각을 잘 안 해보고 무작정 코딩하게 되는 경향이 생기는데, 빨리 대충 코딩하고 틀리고 다시 짜는 것보다 천천히 한 번에 맞히는 것이 훨씬 빠른 것 같다.