2021 국가대표 멘토링 교육 - 2주차

이번 주차부터는 각자 멘토가 배정되어서 문제를 각자 받았다. 나는 4문제를 받았고, 4문제를 모두 풀었다. 사실 그리고 추가문제도 받았는데, 하나도 풀지 못하고 이월되었다.

 

1. 사수아탕

 

굉장히 유명한 문제이지만, 여태까지 풀지 못한 문제이다. 기본적인 관찰으로 0을 기준으로 점점 길게 와리가리하는 것이 최적이라는 것을 알 수 있다. 그러면 구간 dp를 해보고 싶은데, dp식을 세우기가 힘들다. 이때 핵심적인 아이디어는 먹는 사탕 개수를 고정하고 문제를 푸는 것이다. 이제 구간의 크기가 k일 때 방문 순서대로 방문 시간을 t1,t2,..tk라 했을 때, 만약 먹는 사탕 개수를 x개로 고정했다고 했을 때 t1+...+tk+(x-k)*tk의 최솟값을 관리하면 k=x일 때는 m*x에서 이 값을 빼주면 답을 구할 수 있다. 간단한 dp식을 세워서 dp를 구하는 데에 O(N^3), 고정된 먹을 사탕 개수 N가지로 O(N^4)에 문제를 풀 수 있고, 바텀업 방식으로 전이를 잘 상수 시간에 함으로써 dp를 O(N^2)에 구해 문제를 O(N^3)에 구할 수 있다.

 

2. 장난감 정리 로봇

 

답을 이분탐색하자. 답이 x 이하인지 판별하기 위하여, 일단 연약한 로봇들에 치울 장난감을 배정해주자. 작은 무게 제한을 가진 로봇부터 자기가 치울 수 있는 장난감 중 크기가 가장 큰 최대 x개의 장난감들을 치우게 한다. 그리고 이제 남는 장난감들을 작은 로봇들이 치울 수 있는지 판별한다. 똑같이 작은 크기 제한을 가진 로봇부터 장난감을 최대 x개 배당해주면 된다. 구현은 priority_queue를 사용하면 간단하고, 이때 시간복잡도는 O(Nlog^2N)이 되지만 5초라서 100만 엔로그제곱도 든든하게 돈다.

 

3. 핀볼

 

이 문제를 푸는 데에 있어서 핵심적인 아이디어는, 핀볼이 있을 수 있는 위치의 최솟값과 최댓값을 따로 관리해도 된다는 것이다. 블록은 A[i] 이상 C[i] 이하의 위치 최솟값을 C[i]로 바꾸고, C[i] 이상 B[i] 이하의 위치 최댓값을 C[i]로 바꾼다. 뭔가 dp 개형 느낌이 오니 mindp[i]를 핀볼이 있을 수 있는 위치의 최솟값이 C[i]가 되는 상황으로 이 블럭에 도착하게 만드는데에 드는 최소 비용, maxdp[i]를 핀볼이 있을 수 있는 위치의 최댓값이 C[i]가 되는 상황으로 이 블럭에 도착하게 만드는데 드는 최소 비용이라고 한다. 문제의 답은 mindp[i]+maxdp[i]-D[i]의 최솟값이 됨을 알 수 있다. mindp[i]의 값은 j<i이고 A[i]<=C[j]<=B[i]를 만족하는 j에 대하여 mindp[j]+D[i]의 최솟값이고, maxdp[i]의 값은 j<i이고 A[i]<=C[j]<=B[i]를 만족하는 j에 대하여 maxdp[j]+D[i]의 최솟값이다. 이제 세그를 사용하면 될 거 같은 감각이 온다. i를 오름차순으로 보면서, minimum segment tree의 [A[i],B[i]] 구간의 최솟값을 보아 dp값을 구하고 C[i] 위치에 mindp[i]/maxdp[i]를 업데이트해주는 짓을 해주면 dp값 전체를 구할 수 있고 답도 구할 수 있다.

 

4. 컨벤션 센터

 

간단한 그리디를 통하여 어떤 회의 다음에는 그 회의의 끝보다 늦게 시작하는 회의 중 가장 일찍 끝나는 회의가 이뤄지는 것이 항상 최적임을 알 수 있다. 이를 통하여 어떤 회의 i 다음에 이루어질 회의를 nt[i]라 하자. 최대로 이루어질 수 있는 회의 개수는 nt[i] 값들을 이용하여 dp로 구할 수 있다. 이제 사전순 최소의 회의들을 구해야 하는데, 오름차순으로 회의들을 보면서 여태까지 포함하기로 한 회의들에 더해서 이 회의를 포함하는 최적해가 존재하는지를 판별하는 것을 반복하면 된다. 이 방법을 알아보자. 현재 판별하려는 회의를 i라 하고, 포함하기로 한 회의 중 i의 시작보다 일찍 끝나는 회의 중 가장 뒷 회의를 x라 하자. (더미 등을 이용하여 x가 반드시 존재하게 하는 것이 편하다.) 그리고 포함하기로 한 회의 중 x 다음을 y라고 하자. (더미 등을 이용하여 y도 반드시 존재하게 하는 것이 편하다.) 만약 y와 i가 겹친다면 당연히 i를 포함하는 것은 불가능하다. 이제 i가 x와 y 사이에 있다고 생각한다. 원래 x와 y 사이에 들어갈 수 있던 최대 회의 수가 k개라 했을 때, x와 i 사이에 들어가는 회의 개수와 i와 y 사이에 들어가는 회의 개수의 합이 k-1개면 i를 넣어도 무방하다는 것을 알 수 있다. 그 사이에 들어갈 수 있는 회의의 개수는, nt 배열의 스파스 테이블을 만든 후 이를 이용하여 i 직전이나 y 직전까지 이동해서 알 수 있다. x와 y는 set을 이용하여 찾는 것이 편하다. 이러면 문제를 O(NlogN)에 풀 수 있다. NlogN 치고는 20만이 1초 넘게 걸리긴 한다... set의 영향으로 보인다.

 

후기 : 다 풀고 난이도를 보니 플1 다5 다4 다4인데 낮지 않은 난이도인데도 다 풀어내서 기분이 좋다. 물론 그럴 때마다 그래서 왜 국대 떨어졌지 하는 생각에 다시 기분이 안 좋아지긴 한다...