[그리디] 도서관 (1461)(C++)

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

1461번: 도서관

 

 

1. 문제 개요

 

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

 

 

2. 입출력

 

 

3. 문제 풀이

 

다음과 같이 세준이가 6개의 책을 정리해야한다고 가정해보자.

책1,책2,책3은 마이너스 좌표에 있고 책4,책5,책6은 플러스 좌표에 있다.

세준이는 최대 2개의 들 수 있다.

 

직관적으로 생각해보면 세준이는 책1, 책6을 정리하기 위해서는 책1,6이 있는 위치에 무조건 가야한다. 그러나 책2,3,4,5는 책1, 책6을 놓으러 다녀오는 길에 정리하고 올 수 있다.

그렇다면 책을 정리하고 오는 거리를 최소화하는 방법은 무엇일까?

 

책1을 놓고오는 길에 책3을 놓고오면 세준이가 책1,2,3을 놓고오는 거리는 책1의 거리 + 책2의 거리가 된다. 하지만 책1을 놓고오는 길에 책2를 놓고오면 책1의 거리+책3의 거리가 된다. 후자의 값이 더 작으므로 이와같이 그리디하게 선택해주면 된다.

 

또한 음수값을 갖는 좌표와 양수값을 갖는 좌표는 어차피 세준이가 책을 가지고 있는 0의 값에 들려야하므로 별개로 생각할 수 있다.

 

마지막으로 세준이가 0의 좌표값에 돌아오지 않아도 되므로 책1, 책6의 좌표중 거리가 더 먼 좌표를 편도로 다녀오는 것으로 계산해주고 나머지는 왕복으로 계산해주면 된다.

                                                              

 

4. 전체 코드

 

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

using namespace std;

bool compare(int a, int b){
    return a>b;
}

int main(void)
{
    int N, M; //책의수, 한번에들수있는수
    int dist = 0;
    vector<int> positiveV,negativeV; //양수, 음수를 나눠서 저장
    
    scanf("%d%d",&N,&M); //도시 개수
    
    int temp;
    for(int i=0;i<N;i++){
        scanf("%d",&temp);
        if(temp<0) negativeV.push_back(temp);
        else positiveV.push_back(temp);
    }
    
    //절댓값이 큰 순으로 정렬
    sort(positiveV.begin(), positiveV.end(),compare);
    sort(negativeV.begin(), negativeV.end());
    
    int i=0;
    while(i<positiveV.size()){
        dist += (2*positiveV[i]); //왕복 거리 계산 
        i += M; //M만큼 스킵
    }
    i=0;
    while(i<negativeV.size()){
        dist -= (2*negativeV[i]); //왕복 거리 계산 
        i += M; //M만큼 스킵
    }
   //벡터 안에 값이 없는 경우에 0번째 주소를 접근하면 안되므로 다음과 같이 대입
    int temp1=(positiveV.size()==0)?0:positiveV[0];
    int temp2=(negativeV.size()==0)?0:-1*negativeV[0];
    
    //양 끝의 최댓값 중 더 큰 값을 편도로 계산하기 위해 한 번 빼준
    dist -= (max(temp1,temp2));
    printf("%d\n",dist);
}