[백준 1461번] 도서관

[백준 1461번] 도서관

www.acmicpc.net/problem/1461

1461번: 도서관

 

 

 문제

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

 

 입력

  첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치는 0이 아니며, 그 절댓값이 10,000보다 작거나 같다.

 

 출력

 첫째 줄에 정답을 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N,M;
	cin >> N >> M;
	
	vector<int> temp1;
	vector<int> temp2;
	for(int i=0;i<N;i++){
		int a;
		cin >> a;
		if(a<0) temp1.push_back(a);
		else temp2.push_back(-a);
	}
	
	if(!temp1.empty()) sort(temp1.begin(), temp1.end());
	if(!temp2.empty()) sort(temp2.begin(), temp2.end());
	
	int result=0;
	for(int i=0;i<temp1.size();i=i+M){
		int v = -temp1[i];
		result+=2*v;
	}
	
	for(int i=0;i<temp2.size();i=i+M){
		int v = -temp2[i];
		result+=2*v;
	}
	
	if(temp1.empty()) result -= -temp2[0];
	else if(temp2.empty()) result -= -temp1[0];
	else if(temp1[0] < temp2[0]) result -= -temp1[0];
	else result -= -temp2[0];
	cout << result;
	return 0;
}

 그리디 문제로 보자마자 정렬해서 풀면 되겠구나 생각했다. 먼 거리에 있는 책부터 가지고 갈 수 있는 만큼 들고 가도록 생각했고 해당 거리의 2배를 결과에 더해주고 마지막에 모든 책을 정리하고 나면 돌아올 필요는 없기 때문에 가장 멀었던 거리를 한번 더해주도록 하였다.

 첫 시도는 실패였다. 이유는 음수와 양수로 이루어져 있기 때문에 그냥 정렬해버리면 음수의 부분에서는 멀리 있는 것부터 정리하는게 맞지만 양수의 부분에서는 가까운 것부터 정리하게 되기 때문이다. 따라서 양수와 음수를 따로 나누어 정렬하였다. 음수 부분의 책과 양수 부분의 책을 동시에 정리하려고 하면 어차피 원점을 지나야 하기 때문에 상관 없었다.

 두번째 시도도 실패였는데 음수 부분에 책이 없거나 양수 부분에 책이 없거나 하는 예외처리 문제였다. if문으로 가볍게 처리했다.

 

 세번째 시도에 정답입니다를 받을 수 있었다.

 

 문제를 풀면서 algorithm의 sort를 사용할 때 내림차순 정렬이 필요한 경우에 나는 음수를 취해서 그냥 오름차순 정렬을 해오고 있다. 편하긴 하지만 값을 처리하는 과정에서 다시 부호의 변화가 필요하기 때문에 헷갈릴 가능성이 있다. sort의 세번째 인자에 함수를 넣어서 내림차순 정렬을 하는 방법에 익숙해질 필요가 있어 보인다.