RUN@KAIST 7/13 방학 연습 풀이

1. Mountain Road

A 타입 차와 B 타입 차를 분리시키고 생각해 보자. 각각의 그룹에서 먼저 도착한 순서대로 차들을 처리해야 하니, A 차가 현재 몇 대 까지 / B 차가 현재 몇 대 까지 처리되었는지 정도의 상태로 DP를 돌려보자.

A와 B가 항상 교차해서 나온다면 단순히 끝나는 시간만을 고려해주면 되겠지만, 실제로 A 차가 연속하거나 B 차가 연속할 경우에는 일련의 추가적인 규칙들이 있다. 고로, 현재의 DP 상태에서 연속한 A 차를 추가하거나, 연속한 B 차를 추가해서 새로운 DP 상태의 시간을 계산해야 한다. 또한, 마지막에 A를 썼는데 거기에 연속한 A 차들을 추가하면 계산이 꼬이니, 현재의 DP 상태는 단순히 차를 몇 대 쓴 것만이 아니라, 마지막에 무슨 차를 썼는지 역시 저장해야 한다.

정리하면, DP 상태는 현재 몇 대의 A 차를 처리했는지, 몇 대의 B 차를 처리했는지, 마지막에 처리한 차가 무엇인지를 저장한다. 반환값은 물론 최소 시간이다. 마지막에 처리한 차에 따라서, 뒤에 A 차를 연속하게 넣어야 하는지 B 차를 연속하게 넣어야 하는지가 결정된다. 차의 수를 1부터 최대한 늘려가면서, 새로운 시간을 계산하고 이를 dp table에 뿌려준다. 총 N^3 시간에 문제가 해결된다.

새로운 시간을 계산하는 것은, 현재 상태에서 차를 한대 한대 추가하면서, 마지막 차가 시작점에 도착한 시간 / 마지막 차가 끝점에 도착한 시간을 관리하면 된다.

2. Exact Measurement

간단한 그리디 문제이다. 먼저 질량이 1인 계량기만 두고 생각해보자. 질량 1인 계량기로 X % 10을 모두 채울 수 없다면, 가능한 해가 없다. 고로, X % 10을 채울 수 있을 때까지 질량 1인 계량기 패키지를 개수가 많은 순서대로 깐다. 

X % 10을 채웠다면, X는 10의 배수이다. 이제 남은 계량기를 처리해야 한다. 이 때 아직 까지 않은 패키지들은 계량기의 수를 10으로 나누고, 질량 10인 계량기 패키지라고 앞으로 생각한다. 깐 계량기 중에서도 남는 것들이 있을 것인데, 이들의 수를 10으로 나누고, 10짜리 공짜 계량기라고 생각한다. 다음 스텝에서도 질량이 1인 계량기라고 생각하고 똑같이 문제를 해결하는데, 공짜 계량기가 추가 되었으니 그 부분만 처리하면 된다.

3. 링월드

문제 난이도는 모르겠지만 풀이 쓰기는 정말 고역인 문제인거 같다. 졸려서 그런 건지 원래 문제가 그런건지는 잘 모르겠다. 이해하기 힘들어도 나름 최선을 다 했으니 양해 바란다.

원형이 아니라 선형일 때를 생각해 보면 단순한 그리디 알고리즘이 존재한다.

 * 모든 가능한 점들을 0부터 m-1까지 돌면서, 현재 매칭 가능한 구간 중 가장 끝 점이 작은 구간에 매칭한다. 매칭이 된 구간은 버리고 계속한다.

단순하게 O(mlgn) 구현을 하면 안 되니, 매칭될 가능성이 없는 숫자를 빠르게 건너뛰어야 한다. 이는 구간을 시작점 순으로 정렬한 후, 같은 시작점을 가진 구간들을 한꺼번에 처리해 주는 방식으로 O(nlgn)에 priority queue만으로 해결할 수 있다. 그다지 어렵지 않으니 자세한 설명은 생략.

하지만 문제는 원형이라, 이런 방식으로는 해결할 수 없다. 하지만 놀랍게도 해결 방법이 큰 차이가 없다. 원형을 선으로 편 이후, 한 바퀴 돌아가는 구간은 [xi, yi + m] 으로 하나 넣고, 그렇지 않은 구간은 [xi, yi] / [xi + m, yi + m]으로 두 개 씩 넣은 후, 2m 길이의 선에서 배정이 존재하면, 원형에서도 답이 존재한다.

이를 증명해보자. 답 S가 만약에 존재한다면, 두 개씩 배정된 구간에 Si, Si + m 을 각각 배정해 주면 되니까 저 방식으로도 답이 나올 것이다. 하지만, 답이 존재하지 않는데 저 알고리즘에서 답을 뱉는 경우가 존재할 수 있을까? Hall's marriage theorem (홀의 결혼 정리)에 의하면, 임의의 구간들의 부분집합에 대해서, 그 구간들이 덮는 수들의 개수가 구간의 수보다 항상 크거나 같다면 완벽 매칭이 존재한다. 즉, 완벽 매칭이 존재하지 않는다는 것은 구간들이 덮는 수들의 개수가 구간의 수보다 작은 부분집합이 존재한다는 것이다. 

고로, 답이 존재하지 않는다면 이러한 부분 집합이 존재할 것이다. M >= N이라고 가정하자 (아니면 당연히 NO니까.) 만약에 이 부분집합에 속한 구간들의 합집합이 원호 전체를 덮는다고 하면, 가정에 모순이다. 고로 합집합에 항상 구멍이 최소 하나 나 있는데, 이 구멍을 기준으로 위의 원을 편 곳에 사영시켜보자. (한 바퀴 돌아가면 s ~ e + m, 아니면 아무거나 잡고 s ~ e). 그러한 부분집합이 존재한다면, 위에서 원을 선으로 편 형태의 배정에서도 그러한 부분집합을 찾을 수 있다. 고로 저 알고리즘에서도 답을 뱉을 수 없다. 가정에 모순이므로, 저 알고리즘의 결과와 실제 원형에서의 매칭의 존재 유무는 동일하다.

보통 문제 풀이를 쓸 때 직관에서 우러나오는 느낌으로 쓰려고 했는데, 이 문제는 그러니까 산으로 가서 그렇게 작성하지 못했다. 나의 경우에는 처음부터 홀의 정리로 생각을 했는데, 홀의 정리를 계속 쓰다보면 결국 원호상의 길이 N-1 이하의 구간 중, 구간의 길이보다, 구간에 포함되는 구간의 개수가 큰 경우가 존재하는 지를 찾는 문제가 된다. (문장의 첫번째 ~ 세번째 구간은 내가 잡은 모든 길이 N-1 이하의 구간 중 하나를 뜻하고, 네번째 구간은 입력으로 주어진 구간을 뜻한다.) 이를 단순히 계산하면 O(MN^2)인데, 이를 최적화하는 방법을 떠올리다 보면 결국 저러한 선형에서의 문제로 환원해도 상관이 없다는 결론이 나왔다.