[백준/C++] 1461번 도서관

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

1461번: 도서관

문제가 한번에 이해가 안될수도 있으니,, 꼼꼼히 읽어보셔야 한다.

우선, 이 문제는 누가봐도 정렬과 그리디 알고리즘이다.

이 문제를 풀 때 3가지 key point가 있다고 생각한다.

1. 음수부분과 양수부분을 구별 (음수의 개수 세기)

2. m개의 책을 들고 다닐 수 있으므로 m칸씩 이동

3. 맨 끝 값(제일 작은 음수, 제일 큰 양수) 중 절댓값이 더 큰 것을 마지막에 방문 (= 되돌아올 필요 없으니까 x2한 것에서 빼줌)

오름차순으로 일단 정렬한 뒤,  음수 양수 부분 모두 m칸씩 이동하면서 왔다갔다 해야하는 거리를 구한다.

이때 음수 부분은 제일 작은 음수(인덱스 0)부터 시작해주고, 양수 부분은 제일 큰 양수(인덱스 n-1)부터 시작해준다.

제일 먼 곳을 마지막에 방문하기 위함도 있지만, 멀면 멀수록 m권씩 챙겨서 가는게 무조건 이득이기 때문이다!

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n,m,ans,cnt;
vector<int> v;

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

    cin >> n >> m;

    for(int i=0; i<n;i++){
        int num;
        cin >> num;
        v.push_back(num);
        if(num < 0) cnt++;
    }

    sort(v.begin(), v.end());

    for(int i=0; i<cnt;i+=m){ // 음수
        ans += abs(v[i]) * 2;
    }
    for (int i = n-1; i >= cnt; i-=m) { // 양수
        ans += v[i]*2;
    }
    ans -= max(abs(v[0]),abs(v[n-1]));
    cout << ans ;
    return 0;
}