문제

나의 요약

한번에 M권의 책을 들 수 있는데, N개의 책을 원위치로 돌려놔야한다.
책의 위치는 정수 좌표이고, 현재 나와 책들은 0에 위치한다.
모두 돌려놨을때 드는 최소 걸음수를 출력하자.

접근 방법

처음에는 감이 잡히지 않았으나, 테스트케이스들을 보고 직접 한번 정리해보니 금방 규칙을 찾을 수 있었다. 다음 테스트케이스를 보자.

7권의 책이 있고, 우리는 최대 2개를 들고 나를 수 있다.
먼저 책들을 위치별로 정렬한다.
-39 -37 -29 -28 -6 2 11
그 후 음수와 양수 양 극단에서 M개 만큼 들고 나온다.
-39 -37, 2 11을 들고 나오면, 각각 39*2=78, 11*2=22 만큼 걸음을 걷는다.
이후 양수는 더이상 숫자가 없으므로 음수 쪽에서 다시 M개 만큼 들고 나온다.
-29 -28을 들고 나오면 29*2=58 만큼 걸음을 걷는다.
이후 -6을 들고 나오면 6*2=12 만큼 걸음을 걷는다.
다 더하면 78+22+58+12 = 170걸음이다. 여기서 마지막 놔둘 때는 다시 돌아올 필요가 없으므로, 절댓값이 제일 큰 39만큼 다시 빼자. 최종 결과는 170-39=131이다.

이제 이를 일반적인 표현으로 정리해보자.
1. 음수와 양수 양 극단에서 M개씩 들고 나와 2 한 수를 더한다.
1-1. 진행 중 음수와 양수의 개수가 M개 보다 작아지면 남은 개수씩만 들고 나와 2 한 수를 더한다.
2. 이후 절댓값이 제일 큰 수를 빼준다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> books;

void Input()
{
	cin >> N >> M;
	books.assign(N, 0);
	
	for(int i = 0; i < N; i++)
	{
		cin >> books[i];
	}
	sort(books.begin(), books.end());
}

int BookSteps(int startIdx, int endIdx)
{
	if(startIdx == endIdx) { return abs(books[startIdx]); }

	int steps;	
	if(abs(books[startIdx]) >= abs(books[endIdx]))
	{	
		steps = abs(books[startIdx]);
		if(books[startIdx] * books[endIdx] < 0)
		{
			steps += abs(books[endIdx]);
		}	
	}
	else
	{	
		steps = abs(books[endIdx]);
		if(books[startIdx] * books[endIdx] < 0)
		{
			steps += abs(books[startIdx]);
		}
	}
	return steps;
}

void Solve()
{
	int finalSteps = 0;
	int left = 0, right = N-1;
	
	int leftFirstSteps = 0, rightFirstSteps = 0;
	bool isFirst = true;
	while(true)
	{
		int nextLeft = left + M;
		if(nextLeft > N || books[nextLeft - 1] > 0) break;
		
		finalSteps += BookSteps(left, nextLeft - 1) * 2;
		if(isFirst)
		{
			leftFirstSteps = BookSteps(left, nextLeft - 1);
			isFirst = false;
		}
		left = nextLeft;
	}
	
	isFirst = true;
	while(true)
	{
		int nextRight = right - M;
		if(nextRight < -1 || books[nextRight + 1] < 0) break;
		
		finalSteps += BookSteps(nextRight + 1, right) * 2;
		if(isFirst)
		{
			rightFirstSteps = BookSteps(nextRight + 1, right);
			isFirst = false;
		}
		right = nextRight;
	}
	if(left <= right)
	{
		finalSteps += BookSteps(left, right) * 2;
	}
	
	if(leftFirstSteps == 0 && rightFirstSteps == 0)
	{
		finalSteps -= max(abs(books[left]), abs(books[right]));
	}
	else
	{
		finalSteps -= max(leftFirstSteps, rightFirstSteps);
	}
	cout << finalSteps;
}

int main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
  	
  	Input();
  	Solve();
}

풀이한 코드가 매우매우 더럽다.. 이는 양수와 음수를 따로 분리하지 않고 한 배열에서 처리하려고 해서 생긴 문제이다. BookSteps(int, int)를 통해 시작 인덱스와 끝 인덱스를 주었을 때 이들을 '한번에 가려면 얼마의 걸음을 가야하는지'를 반환해준다.

Solve 함수를 보면, 우선 왼쪽에서 음수의 것들만, 오른쪽에서는 양수의 것들만 각각 M개 미만으로 남을 때까지 처리한다. 이후 남은 수들을 대상으로 다시 한번 BookSteps를 진행한다.
그러고 가장 큰 절댓값의 수만큼 빼준다.

회고

접근 자체는 나쁘지 않았는데, 이를 구현하는 과정에서 착오가 있었다. 그냥 음수랑 양수를 따로 나누어 구현했다면 깔끔하게 떨어졌을 것 같은데.. 한번에 처리하느라 인덱스 변수도 복잡해졌다. 또한 M개 미만으로 수들이 남아도 그냥 가장 절댓값이 큰 수를 기준으로 동일하게 처리하면 문제가 없었는데, 이를 생각하지 못하고 굳이 M개로 묶어서 처리해야한다고 생각해서 더 꼬였다.

덕분에 50줄만 나올 코드가 100줄이 나오고 시간도 70분이나 걸렸다..
물론 이 문제는 수열 자체가 하나로 주어져 하나의 배열로 처리해야한다는 생각을 자연스럽게 가지게 된 것 같다.
0을 기준으로 명확하게 나뉘는 수열이였다. 기준이 명확하게 나눠질 수 있다면 굳이 한 배열로 생각하지 말고 나누자.