백준 1461. 도서관

https://www.acmicpc.net/problem/1461

1461번: 도서관

 

처음에 예제의 답이 어떻게 나오는지도 꽤 해맸다.

마지막에 책을 모두 제자리에 놓은 후에는 0으로 돌아오지 않아도 되므로 왕복하지 않아도 된다는 뜻이고,

왕복할때 좌표의 절댓값 * 2가 더해지므로 마지막에 가장 멀리있는 책을 놓으면 된다.

 

또한 음의좌표와 양의좌표를 한번에 가게되면 중간에 0을 들리게 되므로 비효율적이라 따로 생각해야한다.

따라서 음의좌표, 양의좌표를 따로 저장하고 정렬했다.

그후 먼곳부터 모두 m개의 책을 한번에 되돌려놓고, 

마지막에 음의좌표 최댓값, 양의좌표 최댓값중 더 큰값을 빼주면 왕복하지 않게 처리된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m;
vector<int> neg, pos;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        if(num < 0) // 절댓값
            neg.push_back(num * -1);
        else
            pos.push_back(num);
    }

    sort(neg.begin(), neg.end(), greater<>());
    sort(pos.begin(), pos.end(), greater<>());

    // out of bound 방지
    for(int i = 0; i < m; i++)
    {
        neg.push_back(0);
        pos.push_back(0);
    }

    int ans = 0;
    for(int i = 0; i < neg.size(); i+=m)
    {
        ans += neg[i] * 2;
    }
    for(int i = 0; i < pos.size(); i+=m)
    {
        ans += pos[i] * 2;
    }

    // 음수좌표, 양수좌표 최댓값중 가장 큰 값은 마지막에 자리에 놓음으로서 왕복하지 않음
    int bigger = max(neg[0], pos[0]);
    ans -= bigger;
    cout << ans;

}