[boj] 백준 1461 도서관 - 그리디

[문제]

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

1461번: 도서관

 

[풀이]

그리디 알고리즘.

책을 원래자리에 돌려놓기 위해서는 어차피 원점을 지나야 하므로 음수, 양수를 따로 나눠서 계산해준다. m권을 한꺼번에 옮길 수 있다면 왕복값은 m권 중 더 큰 값의 왕복값으로 계산해준다. 그 후, 양 극단에 있는 값 중 더 큰 값에 대해서, 갖다 놓기만 하면 되므로 편도로 계산해주기 위해 값을 빼준다.

예를 들어, -39 -37 -29 -28 -6 2 11 에 대해서 39*2 + 29*2 + 6*2 + 11*2 - 39 = 131이 된다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

int main() {
    //책을 모두 제자리에 둘 때 최소걸음수. 한번에 최대 M권을 들 수 있음.
    int n, m; //책의 개수, 최대로 들고 갈 수 있는 책의 개수
    cin >> n >> m;
    int loc[10001];
    int tmp, minus_cnt = 0;
    for(int i=0; i<n; i++){
        cin >> tmp;
        loc[i] = tmp;
        if(tmp < 0)
            minus_cnt++;
    }


    sort(loc, loc+n);

    //-39 -37 -29 -28 -6 2 11, 극단에 있는 값 중에 가장 큰 값은 왕복 x, 한번만 이동함
    //양수, 음수 따로 왕복값 계산
    
    int answer=0;
    for(int i=n-1; i>=minus_cnt; i-=m){
        answer += (loc[i]*2); //양수 왕복값
    }

    for(int i=0; i<minus_cnt; i+=m){
        answer += abs(loc[i]*2); //음수 왕복값
    }

    answer -= max(abs(loc[0]), abs(loc[n-1]));

    cout << answer;

}