백준 C++ - 도서관(1461) 그리디 알고리즘

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

1461번: 도서관

1. 음수 배열은 내림차순, 양수 배열은 오름차순으로 정렬

 

2. 배열의 요소 개수가 들고 갈 수 있는 책의 배수가 아니라면 횟수를 미리 더하고 시작 지점을 따로 처리

 

3. 시작 지점에서부터 들고 갈 수 있는 책의 개수만큼 증가하며 원점에서 책까지 거리만큼 왔다 갔다 하기 때문에 배열에 있는 거리에다 곱하기 2를 하여 더한다.

 

4. 마지막엔 두 배열 끝 요소를 비교하여 큰 요소를 정답 변수에서 한 번 뺀다. (마지막 책은 돌아올 필요가 없기 때문에 거리가 가장 먼 책을 선택)

#pragma warning(disable:4996)
#include <stdio.h>
#include <queue>
#include<algorithm>
using namespace std;
int n, m, t, ans;
int left[10010], lidx, right[10010], ridx, le, ri;
int check(int x, int y) { return x > y; }
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &t);
		if (t < 0) left[lidx++] = t;
		else right[ridx++] = t;
	}
	sort(left, left + lidx, check); // 음수 배열은 내림차순으로
	sort(right, right + ridx); // 양수 배열은 오름차순으로
	le = ri = m - 1;
    
	if (ridx % m) // 만약 양수 배열의 요소 개수가 m의 배수가 아니라면
	{
		ans += right[ridx % m - 1] * 2; // 나머지만큼의 거리를 미리 계산 후
		ri = ridx % m - 1 + m; // 시작 지점 처리
	}
    
	if (lidx % m) // 음수 배열의 요소 개수가 m의 배수가 아니라면
	{
		ans += left[lidx % m - 1] * -2; // 나머지만큼 거리를 미리 계산 후
		le = lidx % m - 1 + m; // 시작 지점 처리
	}

	for (; le < lidx; le += m) // 들고갈 수 있는 책의 개수 만큼 증가
		ans += left[le] * -2; // 왔다 갔다 하므로 곱하기 2

	for (; ri < ridx; ri += m) // 들고 갈 수 있는 책의 개수 만큼 증가
		ans += right[ri] * 2;

	
	if (-left[lidx - 1] < right[ridx - 1]) // 마지막 책은 다시 돌아가지 않아도 되므로
		ans -= right[ridx - 1];        // 거리가 가장 먼 책의 위치를 한 번만 빼면 끝
	else
		ans += left[lidx - 1];
        
	printf("%d", ans);
	return 0;
}