Fenwick Tree를 이용해야 한다는 힌트를 받아서 생각을 해봤지만... Fenwick Tree를 어떻게 이용해야할 지는 모르겠고, 단지 어떤 작업을 완료하는데 필요한 시간을 구하려면 어떻게 해야할지는 생각해봤다.
어떤 작업을 완료하는 데 필요한 시간은, 어떤 작업을 A라고 하면
1. A 이전 작업들 중
수행시간이 A의 수행시간 이하인 것들의 수행시간의 합과
A의 수행시간을 초과하는 작업들의 수 * A의 수행시간 의 합
2. A 이후 작업들 중
수행시간이 A의 수행시간 미만인 것들의 수행시간의 합과
A의 수행시간 이상인 작업들의 수 * (A의 수행시간-1) 의 합
3. A의 수행시간
1 + 2 + 3 의 값이 어떤 작업 A를 완료하는 데 필요한 시간이 된다.
근데 이것을 그냥 구현했다가는 O(N^2)이 될 것 같아서 Fenwick Tree로 어떻게 해야하나 고민하는 중이었다.
그러다가 질문 게시판을 봤는데 감사하게도 어떤 분이 질문과 함께 자신의 코드를(거의 맞는) 올려 놓으셨다. 코드를 보니 내가 위에서 생각한 방법같아 보이는데 이 것을 Fenwick Tree를 이용하여 구현해 놓으셨다.
https://www.acmicpc.net/board/view/7089
일단 핵심은 각 작업을 수행시간 순으로 정렬하여 먼저 끝나는 작업들 부터 처리한다는 것과 Fenwick Tree에는 현재 남아있는 작업의 개수가 저장된다는 것 이 두 개인 것 같다.
또 막상 하려니 쉽지가 않았고, 내가 제대로 이해하지 못했다는 것을 깨달았다.
결국 제대로 이해한 것 같다. 고민 끝에 이해한 바를 적어보겠다.
라운드 로빈 스케줄링대로 작업을 처리하면, 어떤 작업 A를 기준으로 A보다 수행시간이 짧은 작업이 A뒤에 있든 앞에 있든 A보다 먼저 끝날 수 밖에 없다. 그리고 A와 수행시간이 같은 다른 작업의 경우 A보다 순서상 앞에 있다면 먼저 끝난다.
그래서 정렬을 하고 수행시간이 짧은 작업부터 처리해가면서, 그 과정에서 구한 누적된 값들을 다음 답을 구하기위해 사용한다.
그리고 A가 끝나는데 걸리는 시간을 구하기 위해서 (전체 작업의 개수*A의 수행시간)에서 A의 수행시간 이하, 미만은 그대로 합하는 부분과, A의 수행시간 이상일 때 (A-1)을 합하는 부분을 고려해서 일부를 빼줘야 하는데, 그 부분중 일단 A이후의 작업들의 개수만큼을 빼줌으로써 (A-1)을 합하는 경우를 고려해준다. 나머지 고려사항들을 살펴보면, 일단, A이전의 작업들 중 A의 수행시간을 초과하는 경우는 A값을 더해주니까 이미 처리된 것이고, 이제 생각해봐야 할 것은 A이전의 작업들 중 A이하, A이후의 작업들 중 A미만인 경우이다.
근데 이 경우는 정렬을 통해 A의 수행시간보다 작은(수행시간이 같다면 A보다 앞쪽에 위치한) 작업들을 먼저 처리하면서 A보다 먼저 끝나는 작업이 끝나고 다시 A를 실행하기 까지의 누적된 값을 이용하기 때문에 처리해줄 필요가 없다. 그리고 정렬을 해서 맨 처음에 수행시간이 가장 작은 값부터 처리하기 시작하는데, 이 경우(맨 처음)에는 가장 작은 값이므로 이하, 미만의 값을 처리할 필요가 없다.
겨우 어느정도 이해했는데, 이해한 것을 쓰면서도 다시 헷갈려서 생각해보고... 일단은 많이 어렵다.
다시 읽어보면서 헷갈려서 좀 더 추가로 다시 정리해보면,
(전체 작업의 개수*A의 수행시간)에서 A의 수행시간 이하(이하이면서 A보다 먼저 오는 작업), 미만은 그대로 합하는 부분과, A의 수행시간 이상이고 A보다 뒤에 오는 작업에 대해 (A-1)을 합하는 부분을 고려해서 일부 빼주는 것이 핵심인데,
구현할 때는 먼저 A의 수행시간 이하(이하이면서 A보다 먼저 오는 작업), 미만을 그대로 합하는 부분은 빼주는 방식이 아닌 누적하는 방식을 이용해서 바로 처리한다. 작업 시간 기준으로 정렬된 상태에서, 가장 짧은 것부터 보면서 가장 짧은 것은 이하, 미만의 경우를 고려할 것이 없으므로 (전체 작업의 개수*A의 수행시간, 단 이하, 미만에 대해 처리)에 해당하는 것이 n*time1일 것이고, 두번째로 짧은 것에 대한 (전체 작업의 개수*A의 수행시간, 단 이하, 미만에 대해 처리)는 n*time1 + (n-1)*(time2-time1) 일 것이다. 첫번째 작업은 time1만큼 실행되고 끝났으므로 n*time1에 (n-1)*(time2-time1)을 더해주면 time2의 이하, 미만에 해당하는 작업인 첫번째 작업에대해 처리해준 (전체 작업의 개수*2번재 작업의 수행시간) 이 될 것이다. 이렇게 계속 누적해가면서 다음은 n*time1 + (n-1)*(time2-time1) + (n-1)*(time3-time2) 이 될 것이고 이것은 time3의 이하, 미만에 해당하는 첫번째, 두번째 작업에 대해 처리해준 (전체 작업의 개수*3번째 작업의 수행시간) 이 될 것이다.
결국 여기서 답을 구하기 위해 추가로 필요한 것은 A의 수행시간 이상이고 A보다 뒤에 오는 작업에 대해 (A-1)을 합하는 부분을 처리하는 것 즉 A의 수행시간 이상이고 A보다 뒤에오는 작업의 수만큼을 빼주면 끝이다.
그리고 그 수는 펜윅 트리를 이용해서 (현재 남은 작업의 개수) - (A까지의 작업의 개수) 로 구할 수 있다. 작업시간 순으로 정렬해서 가장 짧은 것부터 끝내면서 A보다 짧은 작업은 다 뺐기 때문에(펜윅트리를 업데이트 해줬기 때문에), A보다 뒤에 오는 작업의 개수를 의미하는 (현재 남은 작업의 개수) - (A까지의 작업의 개수)는 무조건 A의 뒤에 오면서 A이상인 작업들의 개수가 된다.
그리고 위에서 이하이면서 A보다 앞에 온다든지, A의 뒤에 오면서 A이상인 것이라든지... 이상, 이하인 부분의 처리에 대해 헷갈릴 수 있는데, 전혀 문제 없는 것이 sorting을 할 때, 작업에 걸리는 시간기준으로 sorting하고, 작업에 걸리는 시간이 같다면(이상, 이하에 해당) index(작업의 순서를 나타내는 것), 즉 작업의 순서를 기준으로 sorting하기 때문에 전혀 문제 없다.
--------------------------------------------------------------------------------------------
이 문제를 다시 몇 번 풀어봤는데, 풀 때마다 기억이 잘 안나서 블로그에 적어둔 것을 보고 풀었었다. 하지만 이번에는 fenwick tree에 남은 작업의 개수를 저장한다는 아이디어와, 걸리는 시간이 작은 작업부터 본다는 아이디어만 보고, 다른 풀이는 안 본 상태에서 풀이를 생각해 봤다.
일단 정렬을 하되, 작업에 걸리는 시간을 기준으로 오름차순으로 정렬하고 작업에 걸리는 시간이 같다면 실행 순서가 앞인 것을 기준으로 오름차순으로 정렬한다.
즉, 1. 작업 수행 시간과 2. 실행 순서를 기준으로 오름차순으로 정렬하고 앞에서부터 살펴보면 해당 작업은 현재 남아있는 작업 중에서 제일 실행시간이 작기 때문에(혹시 같은 게 여러개 있다면 실행 순서가 제일 앞이기 때문에) 해당 작업이 완료될 때까지 그 작업을 제외한 작업들은 끝나지 않는다. 즉, 해당 작업 완료 시간을 계산하기가 편해진다.
해당 작업을 포함한 해당 작업 앞의 작업들과, 해당 작업 뒤의 작업들로 나눠보면
1) 1초에 한 작업씩 순서대로 실행하기 때문에 해당 작업과 그 앞의 작업들은 해당 작업이 끝날 때까지 각각 해당 작업의 수행 시간만큼 수행된다.
즉, (실행 순서상 해당 작업 이하의 작업들의 수) * (해당 작업 수행 시간) 만큼이 걸린다.
2) 해당 작업 뒤의 작업들을 보자. 뒤의 작업들도 위와 비슷할 것 같지만 하나 다른 점이 있다면 해당 작업이 끝난 후에는 (실행 순서상 뒤에 있으므로) 실행 시간을 계산해줄 필요가 없다. 즉, (실행 순서상 뒤의 작업들의 수) * (해당 작업 수행 시간-1) 만큼이 걸리는 것이다.
결국 한 작업이 끝날 때까지 위의 두 경우에 해당하는 시간의 합(1+2)만큼 걸리는 것이다.
매우 간단해보인다. 하지만 하나 더 생각해야 할 것이 있다.
한 작업이 끝나면 그 작업을 fenwick tree에서 빼줄 것이다. 그렇기 때문에 앞서 끝난 작업들은 계산에 들어가지 않게된다. 결국 앞서 끝난 작업들을 빼고 계산하는 대신, 앞서 끝난 작업들의 수행 시간들만 더해주면 되는 것이다.
추가로 설명하면 앞서 끝난 작업들은 현재 작업보다 수행 시간이 짧거나, 수행 시간이 같아도 실행 순서상 앞에 있는 것들이기 때문에 현재 작업이 끝나기 전에 모두 끝날 수 밖에 없다. 그렇기 때문에 선행 작업들을 빼고 계산한 후 나중에 그 작업들의 수행 시간만 더해주면 된다.
분명 어려운 문제였는데, 풀이를 이해하고도 이걸 어떻게 생각하지? 라고 의문을 가졌던 문제였는데... 이렇게 스스로 생각하고 보니 그리 어렵지 않다. 내가 처음에 너무 어렵게, 복잡하게 접근했던 것 같다. 문제를 여러번 복습하고 하다보니 깨달음이 오는 것 같다. 감사합니다. AC를 받았다!
//그리고 나중에 다시 풀 때, ft.sum(n)부분은 그냥 (n-i+1)로 대체해도 될 것 같다.
댓글 없음:
댓글 쓰기