[백준] C++ 1461번 (도서관)

 

#include <iostream>
#include <algorithm>

using namespace std;

int arrP[51];
int arrM[51];

int main(void)
{
	int a=0;
	int b=0;
	cin>>a>>b;
	
	int P=0;
	int M=0;
	
	for(int i=0; i<a; i++)
	{
		int num=0;
		cin>>num;
		if(num>0)
		{
			arrP[P]=num;
			P++;
		}
		else
		{
			arrM[M]=-num;
			M++;
		}
	}
	
	
	sort(arrP,arrP+P);
	sort(arrM,arrM+M);

	int sum=0;
	
	if(M>b)
	{
		int startM=M%b-1;
		sum+=(arrM[startM]*2);
		
		while(true)
		{
			startM+=b;
			sum+=arrM[startM]*2;
			if(startM==M-1)
			{
				sum=sum-arrM[startM];
				break;
			}
		}
	}
	else
	{
		sum+=arrM[M-1];
	}

	if(P>b)
	{
		int startP=P%b-1;
		sum+=(arrP[startP]*2);
		
		while(true)
		{
			startP+=b;
			sum+=arrP[startP]*2;
			if(startP==P-1)
			{
				sum=sum-arrP[startP];
				break;
			}
		}
	}
	else
	{
		sum+=arrP[P-1];
	}
	
	
	if(arrP[P-1]<arrM[M-1])
	{
		sum+=arrP[P-1];
	}
	else
	{
		sum+=arrM[M-1];
	}
	
	cout<<sum;
	
	return 0;
}

 

 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 문제이다. 이 문제는 일상생활에서 굉장히 많이 접하는 문제이다. 어떻게 하면 가장 효율적으로 이동할 수 있을까??

 

일단 예제 입력 1을 보겠다. 예제 1은 책이 7개 있고 한 번에 2개씩 옮길 수 있다.

일단 정렬을 해준다. 음수부터 살펴보겠다.(5개, 음수를 양수로 바꿔서 계산)

 

이런식으로 정렬된다.

여기서 한 번에 2개씩 옮길 수 있을 때 어떻게 해야 최솟값이 나올까??

6을 먼저 옮기고 (28,29)를 옮기고 (37,39)를 옮기는 것이 최선이다. 합치면 거리는 (6+6)+(29+29)+(39+39)이다.

그럼 한 번에 3개씩 옮길 수 있을 때는 어떻게 될까??

먼저 (6,28)을 옮기고 (29, 37, 39)를 옮기는 것이 최선이다.

이번에는 한 번에 4개씩 옮길 수 있는 경우를 살펴보자.

먼저 (6)을 옮기고 (28,29,37,39)를 옮기는 것이 최선이다.

거리를 최소한으로 움직이기 위해 남는 것을 먼저 옮긴다.

남는 것을 먼저 옮긴다는 말이 뭐냐면 한 번에 2개씩 옮길 때 처음에 6을 먼저 옮겼다. 6을 먼저 옮긴 이유는 6이 갔다가 돌아오는 것이 가장 빠르기 때문이다. 만약 (6,28)->(29->37)->(39) 이렇게 갔다면 훨씬 많이 걸어야 할 것이다. 

총 5개의 책이 있다면 책 5개를 (한 번에 옮길 수 있는 책의 수)로 나눈 나머지 즉 (5%2=1)의 값만큼 먼저 옮긴다는 것이다.

그럼 한 번에 3개까지 옮길 수 있다면?? (5%3=2) 즉 2개를 먼저 옮기고 3개를 옮기는 것이 유리하다.

한 번에 4개까지 옮길 수 있다면 5%4=1 즉 1개를 먼저 옮기고 4개를 옮기는 것이 유리하다.

 

이러한 방법으로 양수와 음수를 나눈 후 최소 걸음 수를 계산해 주면 된다.

양수와 음수 중 마지막 값이 더 큰 값은 sum에서 빼주면 된다.(마지막에는 돌아올 필요가 없기 때문에 가까운 쪽은 먼저 갔다가 마지막에 먼 쪽을 가면 되기 때문이다.)