[BOJ/백준][Gold5] 1461 : 도서관 (C++)

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

1461번: 도서관

 

 

[난이도] Gold5
[유형] Greedy

[풀이]
음수인 좌표와 양수인 좌표를 각각 a,b vector에 저장한 뒤 따로 생각해줍니다.
가까운 위치에 있는 좌표부터 M개씩 책을 가져다 놓으면 됩니다.
만약 vector의 크기가 아래와 같이 M으로 나누어 떨어지지 않는다면
아래와 같이 5%2 = 1 번째 책부터 옮겨주면 됩니다.
왜냐하면 가까운 곳을 먼저 왕복해 주는것이 유리하기 때문입니다.

(M==2)
0      0+M     0+2M
-6 -28 -29 -37 -39

위와 같이 옮기면 6*2+29*2+39*2 = 158 이 됩니다.

  M
2 11
좌표가 양수인 크기 2 벡터는 위와 같이 M번째만 방문하면 두 책을 모두 옮길 수 있으므로
11*2=22 이 됩니다.

여기서 마지막으로 책을 가져놓은 좌표에서 다시 0으로 돌아오지 않아도 되므로
0에서 가장 먼 좌표가 포함되어 있는 음수 vector를 나중에 처리하는 것이 유리합니다.
그러므로 -39 좌표의 책을 옮긴 뒤에 0으로 돌아오는 것은 고려하지 않아도 되므로
158+22-39 = 131이 최종 정답이 됩니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<int> a,b;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(v>0) a.push_back(v);
        else b.push_back(-v);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans=0;
    if(!a.empty()){
        for(int i=a.size()%M-1;i<(int)a.size();i+=M){
            if(i>=0) ans+=a[i]*2;
        }
    }
    if(!b.empty()){
        for(int i=b.size()%M-1;i<(int)b.size();i+=M){
            if(i>=0) ans+=b[i]*2;
        }
    }
    if(a.empty()) ans-=b.back();
    else if(b.empty() || a.back()>b.back()) ans-=a.back();
    else ans-=b.back();

    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1461.cpp