[BOJ 1461] 도서관

풀이

모든 좌표를 왕복하지만 제일 먼 좌표를 한번만 가게되면 최소 거리가 나온다는 아이디어를 가지고 풀이하였다. 입력 데이터에 0을 삽입하여 오름차순 정렬 후 처음 ~ 0의 위치 인덱스전까지 M개씩 건너뛰면서 배열값의 2배를 더해주고 똑같은 방식으로 마지막 ~ 0의 위치 인덱스 후까지 M개씩 건너뛰면서 배열의 값 2배를 더해준다. 그리고 첫번째 배열 값과 마지막 배열 값을 비교하여 더 큰 값을 한번 빼주면 정답이 나온다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m;
int arr[10001];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	sort(arr, arr + n + 1);
	int t;
	for (int i = 0; i <= n; i++) {
		if (arr[i] == 0) {
			t = i;
			break;
		}
	}

	int ans = 0;
	for (int i = 0; i < t; i += m) ans += 2 * abs(arr[i]);
	for (int i = n; i > t; i -= m) ans += 2 * abs(arr[i]);


	cout << ans - max(abs(arr[0]), abs(arr[n]));

	return 0;
}