[BAE/<JOON> 문제풀이] 1461. 도서관

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

1461번: 도서관

 

핵심::

m권의 책을 한번에 옮길 수 있고 멀리있는 책부터 복구 시키면 총 m권의 책을 복구하는데 { max(m) * 2 } 의 비용이 든다.

또한 복구를 완료하면 0 으로 돌아올 필요가 없으므로 마지막 m권의 책을 복구하는데에는 { max(m) } 의 비용이 든다.

 

풀이::

멀리있는 책일 수록 비용이 늘어나고 연속된 m권에 대해서는 가장 멀리있는 책의 비용만 지불할 수 있으므로

 

책들의 위치를 음수와 양수로 나눠 따로 저장하고 가장 멀리있는 책부터 시작해서 m권씩 저장하고 남는 책들을 정리하면 가장 효율적으로 비용을 처리할 수 있다.

 

의견::

문제 제한 시간이 2초이고 책이 최대 10000권인데 O(N) 풀이가 나오는 점이 살짝 의아하다.

 

거진 2달 쉬었는데 재활 훈련 너무 힘들다... 회사 힘들어

 

코드::

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

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> pos, neg;
	int posm = -1, negm = -1;

	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		if (a > 0) {
			pos.push_back(a);
			posm = posm > a ? posm : a;
		}
		if (a < 0) {
			neg.push_back(abs(a));
			negm = negm > abs(a) ? negm : abs(a);
		}
	}

	sort(pos.begin(), pos.end()); sort(neg.begin(), neg.end());
	
	int sum = 0;

	if (negm > posm) {
		int s = pos.size() % m;
		if (s > 0) {
			sum += pos[s - 1] * 2;		
		}	
		for (int i = s; i < (pos.size() - m + 1); i += m) {			
			if (i + m - 1 >= pos.size()) break;			
			sum += pos[i + m - 1] * 2;
		}

		s = neg.size() % m;
		if (s > 0) {
			sum += neg[s - 1] * 2;
		}
		for (int i = s; i < (neg.size() - m + 1); i += m) {
			if (i + m - 1 >= neg.size()) break;
			sum += neg[i + m - 1] * 2;
		}

		sum -= neg[neg.size() - 1];
	}
	else {
		int s = neg.size() % m;
		if (s > 0) {
			sum += neg[s - 1] * 2;
		}
		for (int i = s; i < (neg.size() - m + 1); i += m) {
			if (i + m - 1 >= neg.size()) break;
			sum += neg[i + m - 1] * 2;
		}

		s = pos.size() % m;
		if (s > 0) {
			sum += pos[s - 1] * 2;
		}
		for (int i = s; i < (pos.size() - m + 1); i += m) {
			if (i + m - 1 >= pos.size()) break;
			sum += pos[i + m - 1] * 2;
		}
		
		sum -= pos[pos.size() - 1];
	}

	cout << sum;

	return 0;
}