[IOI][2014] 선물 + 작업 배치 (FB)

문제 : 선물 (IOI 2014)

원형 테이블을 L개의 구역으로 나누었다. 각 구역은 차례로 0부터 L-1까지 번호가 매겨져 있고, 총 N명의 사람들이 이 구역 중 하나에 앉아 있다. 이제 이 사람들에게 N개의 선물을 나누어주고 싶다. 선물은 0번 구역에 있고, 인접한 구역으로 이동하는데 1초가 걸린다. 선물은 한 명이 들고 나누어주는데, 이 사람은 최대 K개의 선물을 들 수 있다. 모든 사람들에게 선물을 나누어 주는 최소 시간을 구하는 프로그램을 작성하시오.

아이디어 : 선물 (IOI 2014)

원에서 0의 위치에서 가장 멀리 있는 사람의 위치를 생각해보겠습니다. 어쨌든 이 사람에게 선물이 전달되어야 하기 때문에 최악의 상황을 먼저 제거하는 것은 옳은 방법일 것입니다. 만약 가장 멀리 있는 사람의 위치가 0 지점에서 정반대일 때, 이 사람에게 선물을 주고 돌아오는 경우가 있을 것입니다. 이 때 돌아오는 길은 받드시 자신이 걸어온 길로 돌아온다고 하겠습니다. 또한 최대 K 개의 선물을 들 수 있기 때문에 0 지점에서 가장 반대편에 있는 사람에게 가는 동안에 만나는 최대한 멀리 있는 K-1 명의 사람들에게 선물을 주면서 지나가고 가장 멀리있는 사람에게 마지막 선물을 준다고 해보겠습니다. 가장 마지막에 있는 사람에게 선물을 주는 순간, 손에는 더이상 선물이 없기 때문에 0지점으로 돌아가야 합니다. 0으로 돌아가는 경우에도 최단거기로 가야하기 하는데 0지점에서 정반대에서 0으로 갈 때에는 원의 어느 방향으로 돌아가도 상관이 없습니다. 하지만 여기서는 꼭 돌아온 길을 사용해서 0 지점으로 간다고 하겠습니다.

만약 가장 먼 지점에 있는 사람이 정반대점에서 조금이라도 벗어난 위치에 있다면, 들고 있는 K개의 선물 중에서 가장 마지막 선물을 가장 멀리 있는 사람에게 준 뒤에 돌아와야합니다. 이 경우에는 걸어온 길을 이용해서 0지점으로 돌아오는 것이 최적입니다.

교수님께서 설명해주신 부분은 여기까지입니다. 이러한 상황에서 최적인 방법이 있을 때, 0에서 시계방향으로 선물을 주고 돌아오는 길과 반시계방향으로 선물을 주고 돌아오는 길이 교차할 수 없다.라는 이유로 원을 잘라서 생각할 수 있다고 했습니다. 그리고 이렇게 자른 선형 경로에서 Greedy 탐색을 진행하면 하나의 값을 찾을 수 있다고 하셨습니다. 이 방법을 모든 l에 대해서 적용해서 가능한 모든 방법을 자르고 Greedy 탐색을 진행해서 이들의 최소값을 구하면 정답에 근사한 값을 찾을 수 있다고 하셨습니다.

그러나 이러한 방법은 선물을 주고 돌아올 때 온 길을 돌아오는 것보다 한바퀴를 도는게 나을 수 있다.라는 것을 배제한 간략한 풀이입니다. 한 번 더 생각해볼 부분이, K개의 선물을 들고 가장 먼 지점에 있는 사람에게 선물을 주었는데, 0지점부터 현재까지 오는 동안에 만난 사람이 K명보다 적은 경우입니다. 이 경우에는 걸어온 길로 0지점으로 돌아오는 것보다 원의 절반 지점을 넘어서 남은 선물을 주고 오는 것이 더 최적일 수 있습니다.

//나에게 보내기 카톡에서 검색 : 선물 : 손으로 그린 그림 나옴

문제 : 작업 배치 (FB)

여러가지의 작업이 있고, 이 작업을 A~Z로 표현하자. 작업 하나를 끝나는데 시간 1이 걸린다. 한 작업을 끝내면 k번은 다른 작업을 해야 한다. N개의 작업이 문자열로 주어졌을 때, 모든 작업을 가장 빠른 시간에 끝내는 배치를 구하시오. 예를 들어 AAABBBCCC, k=2가 주어진다면 최적의 배열은 ABCABCABC (또는 ACBACBACB)로 총 시간 9가 걸리고, AAABC, k=1이 주어진다면 ABACA (또는 ACABA)로 총 5가 걸린다.

아이디어 : 작업 배치 (FB)

가장 많이 수행해야 하는 작업이 있다면 이 작업을 할 수 있는 순간에는 쉬지 않고 이 작업을 진행해야지 최적의 값을 찾을 수 있을 것입니다. 가장 많은 작업을 찾기 위해서는 기본적으로 정렬을 해야하는데, 매번 하나의 작업을 수행하고 전체를 정렬하는 것은 최적이 아닌 것으로 생각됩니다.

그래서 MAX HEAP을 사용합니다. 가장 우선순위가 높은 작업이 ROOT 올라오는 HEAP을 하나 만드는 방법을 생각해보겠습니 다. MAX HEAP에 들어가는 데이터는 {작업 : (남은 작업의 수, 최근에 실행한 시간)} 입니다. 남은 작업의 수가 많은 수록, 최근에 실행한 시간이 작을 수록 Root로 올라갑니다.

여기에 큐 하나를 추가하면 이 문제를 해결할 수 있습니다. AAABBBCCC, k=2라면 처음에는 아무 작업도 배정되지 않았으므로 힙에 A: (3, 0), B: (3, 0), C: (3, 0)이 들어 있습니다. 힙 : 이 자리에 올 수 있는 작업, 큐 : 나중에 올 수 있는 작업을 의미합니다.

1. i=1: 힙의 루트가 A라면 A를 내보내고, 힙에서 A를 제거한다. 다음, 큐에 A: (2, 1)을 추가한다. A
2. i=2: 다음, 힙에는 B, C가 들어있고, 둘 중 하나 B를 뽑아낸다면 큐에 A: (2, 1), B: (2, 2)를 추가한다. AB
3. i=3: 힙에는 C만 들어 있고, C를 뽑아낸다. 이제 힙은 비어 있고, 큐에는 A: (2, 1), B: (2, 2), C:(2, 3)이 들어있다. ABC
4. i=4: 힙이 비어 있을 때는 큐를 사용한다. 큐의 맨 앞에 있는 원소가 A: (2, 1)이므로 A가 이제 할 수 있는 일이다. 큐에서 제일 앞에 있는 원소를 빼서 힙에 넣는다. 힙에는 지금 하나의 작업만 남아있으므로 힙의 루트가 A이고 A를 내보낸다. 그리고 힙에서 A를 제거한다. 다음, 큐에 A: (1, 4)을 추가한다.
5. i=5: 큐의 맨 앞에 B: (2, 2)이 들어 있으므로 이 값을 빼서 힙에 넣고, 루트를 제거하면 ABCAB. 다시 B: (1, 5)를 큐에 넣는다.
6. 반복

만약 큐가 이렇게 해도 비어 있다면 _를 출력한다. (이 시간에 아무것도 하지 않는다)

시간 복잡도

하나의 노드가 힙에 들어갔다가 나오고 큐에 들어갔다가 나오는데 $O(logN + 1)$시간이 걸리고, 모든 노드에 대해서 이를 진행하므로 $O(NlogN)$이 걸린다. 문제에 따라서 N이 문자만 가능한 경우면 N=26이므로 시간복잡도가 의미를 가지지 않고, 작업의 번호가 자연수이고 N이 충분히 크다면 위 시간 복잡도는 의미를 가집니다.