*[백준][1461] 도서관

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

1461번: 도서관

문제

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

입력

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

출력

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

 

 

풀이 과정

1. 음수와 양수 2가지 경우를 따로 계산하였다.

2. 오름차순으로 정렬 후 가장 먼 곳을 기준으로 M개씩 증가시켰다.

   -> 먼 거리를 기준으로 가면서 연속 된 M 만큼의 책을 놓을 수 있으며, 다음 방문 할 곳은 M개 정리 한 후의 최댓값이 된다.

3. 마지막은 0으로 복귀하지 않아도 되기 때문에, 음수와 양수 중 더 먼곳을 마지막에 방문하도록 했다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
bool asc(int &a, int &b) {
	//오름차순
	return a > b;
}
bool desc(int &a, int &b) {
	return a < b;
}
int main()
{
	int N, M;
	vector<int> negative;
	vector<int> positive; 
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		int n;
		scanf("%d", &n);
		if (n >= 0) {
			positive.push_back(n);
		}
		else {
			negative.push_back(abs(n));
		}
	}
	sort(positive.begin(), positive.end(), asc);
	sort(negative.begin(), negative.end(), asc);

	int answer = 0;
	for (int i = 0; i < positive.size(); i+=M) {
		answer += positive[i] * 2;
	}
	for (int i = 0; i < negative.size(); i+=M) {
		answer += negative[i] * 2;
	}

	if (!negative.empty() && !positive.empty()) {
		answer -= max(negative[0], positive[0]);
	}
	else if (!negative.empty()) {
		answer -= negative[0];
	}
	else {
		answer -= positive[0];
	}
	printf("%d\n", answer);
	return 0;
}

 

결과