BOJ 1461 - 도서관

www.acmicpc.net/problem/1461

1461번: 도서관

 

정리해야될 책의 위치와 처음에 세준이 위치한 좌표값은 0 이다.

 

최대 들고 갈 수 있는 책의 수가 M개 이고, 

좌표이동을 해서 책을 제자리로 돌려 놓을 때, 한 칸 이동할때 걸음수를 1이라 하고 

최소 걸음수를 계산해야 한다.

 

주의할점은 책을 놓고 간 뒤, 다시 놓아야될 책이 있으면 시작좌표인 0으로 되돌아 와야 한다는 점이다.

그리고 마지막으로 책을 다 놓으면 다시 시작좌표로 되돌아 올 필요가 없다.

 

그래서, 가장 먼저 떨어진 것을 제일 나중에 처리해주는게 좋다.

(가장 먼저 떨어진 것을 마지막이 아닌 처음이나 도중에 처리하면 다시 돌아와야 하므로 거리가 더 늘어남)

 

또 하나 생각해봐야 할 것은, 음수인 위치와 양수인 위치에 대한 처리이다.

부호가 교차하는 서로 다른 점들을 선택해서 처리하면, 같은 부호를 처리할때 보다 더 많은 거리를 가야할 수도 있다

그래서 놓을 책들을 선정할때, 같은 부호인 것 끼리 잡는게 좋다.

(정렬시에 sort(arr, arr + n + 1) 인 것은 0을 추가하기 위함임)

 

 

문제의 예제 입력 1을 예제로 들면,

N = 7, M = 2

arr = [-37, 2, -6, -39, -29, 11, -28] 이다.

 

먼저 계산을 좀 더 편하게 하기 위해, 오름 차순으로 정렬해주고,

음수 일때, 양수 일때 나눠서 순회하는데, 하나씩 비교하는게 아니라 M개씩 묶어서 순회한다.

묶을 때 이런식으로 묶을 수 있다.

(-39, -37), (-29, -28), (-6), (2, 11)

 

-6 만 따로 인것은 -6 다음이 부호가 양수여서 부호가 교차하기 때문이다.

 

이 묶음을 가지고 거리를 계산하면

29 * 2 + 6 * 2 + 11 * 2 + 39 = 131 이 된다.

(39 를 제외한 나머지는 책을 놓고 다시와야 하기 때문에 2배가 되고, 39 는 마지막이므로 놓고 다시 안오기 때문에 2배가 아니다)

 

 

 

- c++

#include <algorithm>
#include <cmath>
#include <iostream>
 
#define MAX 10001 
 
using namespace std;
 
int n, m, answer;
int arr[MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> arr[i];
    
    sort(arr, arr + n + 1); // arr + n + 1 인 것은 0을 포함하기 위함임.
    
    int idx;
    for (int i = 0; i <= n; ++i) {
        if (arr[i] == 0) {
            idx = i;
            break;
        }
    } 
    
    // 음수 
    for (int i = 0; i < idx; i += m) answer += abs(arr[i] * 2);
    // 양수
    for (int i = n; i > idx; i -= m) answer += arr[i] * 2;
 
    answer -= max(abs(arr[0]), arr[n]);
    cout << answer;
 
    return 0;
}