[BOJ] 백준 1461 도서관

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

 Input 

7 2

-37 2 -6 -39 -29 11 -28

 

 Output 

131

마지막에 모든 책을 놓는 순간을 제외하고는 0 지점에 돌아와서 갖다놓을 책을 들어야 합니다.

따라서 0 지점을 중심으로 접근할 수 있습니다.

가령, {-3, 1, 2}가 있다면 음수/양수를 구분해서 책을 갖다놓는 것이 이득입니다.

→ {-3}, {1, 2}

그렇다면 어떤 묶음을 마지막으로 갖다놓는 것이 이득일까? 

제일 먼 거리에 위치한 묶음을 마지막으로 처리하면 다시 돌아올 필요가 없으므로 이득입니다.

따라서 {1, 2} → {-3} 으로 갖다 놓아서 걸음 거리 = (2*2) + (3) = 7 

 

 

Test Case 분석

한번에 들 수 있는 책의 개수가 2개이므로 다음과 같은 묶음으로 처리됩니다.

{-39, -37}, {-29, -28}, {-6}, {11, 2}

두 영역(음수 / 양수) 중에서 가장 거리가 먼 지점은 -39이므로 다음과 같이 계산할 수 있습니다.

걸은 거리를 구하면 131 = (29*2) + (6*2) + (11*2) + 39

(중간에 어떤 순서로 가져다 놓는 것은 상관이 없습니다.)

 

 

구현 사항

책이 놓이는 지점을 sort합니다.

m권씩 들 수 있으므로 0을 기준으로 갖다놓고 돌아오는 거리를 구해줍니다.

마지막에 가장 먼 거리는 다시 0 지점으로 돌아올 필요가 없으므로 해당 거리만큼만 제외합니다.

---

#include<iostream>
#include<algorithm>
using namespace std;
 
int n, m, pos[10001], answer=0;
int main(){
    cin >> n >> m;
    for(int i=0;i<n;++i)
        cin >> pos[i];
        
    sort(pos,pos+n+1);
 
    // 0인 지점 구하기
    int pivot=0;
    for(int i=0; i<=n; ++i){
        if(pos[i] == 0){
            pivot = i;
            break;
        }
    }
 
    // 음수 영역    
    for(int i=0; i < pivot; i += m)
        answer += abs(pos[i] * 2);
    
    // 양수 영역
    for(int i=n; i > pivot; i -= m)
        answer += pos[i] * 2;
    
    // 최대로 갔던 거리를 마지막으로 간 것으로 되도록 처리
    answer -= max(abs(pos[0]), abs(pos[n]));
    
    printf("%d", answer);
}