https://www.acmicpc.net/problem/1461
문제 정리: 양의 방향과 음의 방향으로 책을 가져다 둬야하는데 한번에 M개의 책을 갖고 갈 수 있으며 마지막에는 제자리로 돌아올 필요가 없다.
문제풀이 순서는 다음과 같다.
1. 책을 양의 방향에 있는 책과 음의 방향에 있는 책으로 나눈다.
2. 각 방향에 있는 책들을 정렬하여 멀리 있는 책들부터 거리를 구할 수 있게 한다.
※ 음의 방향은 그대로 정렬, 양의 방향은 내림차순으로 정렬
3. 각 방향에 책이 없어질 때까지 M개의 책을 빼낸다. 책을 빼낼 때 첫번째로 빼는 책은 distance리스트에 저장해둔다.
4. distance리스트를 오름차순으로 정렬하여 가장 큰 값을 제외하고는 x2를 하여 더하고 큰 값은 그냥 더해준다.
※ 최소 걸음수를 구하는 문제이기에 가장 먼 거리를 편도로 이동하고 남은 거리는 왕복으로 이동한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 총 책의 개수
int M = Integer.parseInt(st.nextToken()); // 한번에 들 수 있는 책의 개수
ArrayList<Integer> negative = new ArrayList<>(); // 음의 번호에 가야하는 책
ArrayList<Integer> positive = new ArrayList<>(); // 양의 번호에 가야하는 책
st = new StringTokenizer(br.readLine());
for (int i=0; i<N; i++) {
int book = Integer.parseInt(st.nextToken());
if (book > 0) positive.add(book);
else negative.add(book);
}
Collections.sort(negative);
Collections.sort(positive, Collections.reverseOrder());
ArrayList<Integer> distance = new ArrayList<>();
// 음의 위치부터 책 정리
while(!negative.isEmpty()) {
int temp=0; // 이동해야하는 거리
temp = negative.remove(0);
for (int i=1; i<M; i++) {
if (!negative.isEmpty()) {
negative.remove(0);
}
}
distance.add(-temp);
}
// 양의 위치 책 정리
while(!positive.isEmpty()) {
int temp=0; // 이동해야하는 거리
temp = positive.remove(0);
for (int i=1; i<M; i++) {
if (!positive.isEmpty()) {
positive.remove(0);
}
}
distance.add(temp);
}
int result = 0;
Collections.sort(distance); // 가장 먼 거리를 알기 위해 sort
for (int i=0; i<distance.size(); i++) {
// 가장 먼 거리만 편도로 이동, 남은 거리는 왕복이라 x2
if (i == distance.size()-1) result += distance.get(i);
else result += (distance.get(i)*2);
}
System.out.println(result);
}
}