백준 1461 도서관 - C++, 그리디 알고리즘, 정렬

1461번: 도서관

#include <iostream>
#include <algorithm>
using namespace std;
int book[10001];
int main(){
    int n, m, count = 0;
    int answer = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> book[i];
        if(book[i] < 0)
            count++;
    }
    
    sort(book, book + n);

    // 다 이동을 한 후 제일 먼 거리를 마지막에 간걸로 처리하면 된다

    for(int i = 0; i < count; i += m)
        answer += abs(book[i] * 2);

    for(int i = n - 1; i >= count; i -= m)
        answer += book[i] * 2;

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

    cout << answer << '\n';
}

---

문제가 그리디 알고리즘을 사용한다는것에서 아이디어를 조금 가져왔습니다.

 

1. 일단 정렬

2. 그 다음 모든 책을 왕복으로 간다고 생각

3. 그런 다음 제일 큰 값을 맨 마지막에 갔다고 침

 

입력을 받을 때 양수와 음수를 나눠줄 필요가 있었고 이는 입력시 받는 음수의 양으로 카운트했습니다.

(0을 추가해 피벗으로 사용하는 코드들이 있었는데 한번 탐색을 한다는 점에서 시간적 손해가 있었습니다)

 

이루 포문을 음수, 양수 순으로 해준 뒤 마지막에 제일 큰 수를 한번 제외(왕복 -> 편도)하면 됩니다. 이때 abs를 사용해야 모든 수가 음수/양수일때 예외가 생기지 않게 됩니다.