https://www.acmicpc.net/problem/1461
0의 위치에 있는 책들을 한 번에 최대 M개씩 옮겨 모두 제자리로 옮기는 최소 걸음을 구하는 문제이다.
책의 개수, 한번에 옮길 수 있는 책 개수 모두 50 미만으로 굉장히 작은 수여서 우선 동선 파악을 위해 정렬을 하였다.
그 다음으로 어떤 동선을 선택해야 정답에 해당하는 값이 나올 수 있는지 먼저 파악하기로 했다.
첫 번째 예제로 과정을 생각해보았다.
-39 -37 -29 -28 -6 2 11
처음에는 현재 위치인 0에서부터 그때그때 가까운 지점을 놓는다 생각해보았다.
0에서 2, 2에서 -6 이후 0으로 돌아와 다시 11, -28로 이동하고 돌아오는 방식이었다.
하지만 양수에서 음수, 음수에서 양수 위치로 번갈아 가며 놓는 것은 0에서 다시 책을 집을 수 있는 기회를 놓치며 동선 낭비가 되는 것을 느꼈다.
다음 생각한 방법으로는 양수, 음수지역을 나누어 처리하는 것이었다.
-39 -37 -29 -28 -6 2 11
양수인 2, 11을 처리하고, 모든 양수를 처리한 뒤 -6과 -28, -29와 -37 순서로 가까운 책들을 M개씩 순서대로 처리하는 방법이다.
하지만 위 방법으로 처리하면 양수 처리에 22, 음수 처리에 56 + 74 + 39만큼의 비용이 들어 131이 나올 수 없었다.
그래서 131이 나올 수 있는 상황을 생각해보았다.
먼저 양수쪽은 22가 최선으로 보이고, 음수쪽을 어떻게 처리하는 것이 좋은지 보았다.
-6 하나를 처리하고 12보, -28과 -29를 처리하고 58보, 마지막으로 -37과 -39를 처리하고 39보로 마무리하면 정답인 131보가 나왔다.
이 계산방법을 통해 풀이방법에 대한 가설을 세워봤다.
- 음수와 양수를 따로 쭉 계산한다.
- 한 부분에서 (음수 or 양수) 처리되지 않은 위치의 개수가 M개의 배수일 경우 M개씩 처리한다.
- 한 부분에서 처리되지 않은 위치의 개수가 M개의 배수가 아닐 경우 가까운 (개수 % M)개의 책부터 처리한 뒤 나머지를 M개씩 처리한다.
- 마지막 책을 처리한 뒤 0으로 돌아올 필요가 없으므로 음수와 양수 각 부분의 위치 절댓값의 최댓값을 비교하여 큰 쪽을 마지막으로 처리한다.
위 로직으로 두 번째 예제를 풀이해보았다.
-45 -26 -18 -9 -4 22 40 50
먼저 4번 로직에 의해 |-45|와 50 중 50이 더 크므로, 음수 부분을 먼저 처리하여 50 위치에서 0으로 돌아오지 않아도 되도록 한다.
음수 부분의 처리 개수가 5개이므로, 5 % 3 = 2개 만큼 0에서 가까운 순서로 처리한다. (-4와 -9를 먼저 처리해 18보 추가)
그리고 나머지 3개를 처리한다 (왕복 90보 추가)
다음 양수 부분이 3개 이므로 양수 3개를 처리한다 (50보 추가 후 완료)
결과는 18 + 90 + 50 = 158보로 예제 정답과 동일함을 알 수 있다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(' ').map{it.toInt()}
val minPq = PriorityQueue<Int>(reverseOrder())
val plusPq = PriorityQueue<Int>()
readLine().split(' ').map{it.toInt()}.forEach {
if(it >= 0) plusPq.offer(it)
else minPq.offer(it)
}
var moves = 0
var minLastMove = 0
while(minPq.isNotEmpty()){
if(minPq.size % M != 0){
var last = 0
for(i in 1..(minPq.size % M))
last = minPq.poll()
minLastMove = last
moves += last*(-2)
}else{
var last = 0
for(i in 1..M)
last = minPq.poll()
minLastMove = last
moves += last*(-2)
}
}
var plusLastMove = 0
while(plusPq.isNotEmpty()){
if(plusPq.size % M != 0){
var last = 0
for(i in 1..(plusPq.size % M))
last = plusPq.poll()
plusLastMove = last
moves += last*2
}else{
var last = 0
for(i in 1..M)
last = plusPq.poll()
plusLastMove = last
moves += last*2
}
}
val answer = if(plusLastMove >= -minLastMove) moves - plusLastMove
else moves + minLastMove
print(answer)
}양수 부분과 음수 부분을 처리할 Priority Queue를 각각 생성하고 음수의 경우 reverseOrder로 설정해 원점에서 가까운 순으로 뽑아오도록 하였다.
다음, 음수와 양수 각각 부분에 대해 위에서 언급한 로직으로 처리하는 코드를 담았고 moves변수에 모든 왕복 거리를 구한 다음 양수쪽 가장 긴 거리와 음수쪽 가장 긴 거리중 절댓값이 큰 값을 빼줌으로써 마지막에 원점으로 돌아오지 않는 부분을 만족시켰다.
