백준알고리즘 11399. ATM 해설과 소스

백준 알고리즘 11399번을 풀이했는데,

엉뚱한 문제로 꽤나 고생했습니다 ㅎ..
​

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

11399번: ATM

분명 제 PC에서는 랜덤으로 1000건의 데이터를 생성해서 풀이해봐도 이상이 없는데

백준 사이트에서 채점만 하면 틀리는 것이 문제였었는데,

천신만고 끝에 문제원인을 발견하였습니다.

​

원인은 memcpy 명령어에 있었습니다.

memcpy 명령은 대상 주소에 원본주소를 특정길이만큼 복사하는 기능인데요.

​

만일 long 포인터가 다음과 같이 정의되어 있다면

n=1000;
long *arr  new long[n];
      :

 다음과 같은 명령어를 사용하는 것은 문제가 없습니다.

memcpy(arr, arr+1, sizeof(long) * 10);

문제는 아래와 같은 명령어를 사용할 때입니다.

memcpy(arr+1, arr, sizeof(long) * 10);

PC 에서는 10개 항목이 제대로 복사되지만,

백준 사이트에서는 다르게 처리되는 것으로 추정됩니다.

​

크레이의 컴퓨터감각(?) 으로는 첫번째 데이터가 두번째 복사되고, 두번째 데이터가 세번째 복사될 때 복사되었던 첫번째 데이터를 사용하여 연쇄적으로 동일한 데이터가 복사되는게 아닐까 생각되는데,
아마도 가상화 서버 시스템이 그렇게 처리하는 것으로 추정됩니다.

​
혹시나 해서 이 부분을 for 루프로 바꾸어 복사하도록 하니까 정상 패스~되었습니다 ㅎㅎ
하지만 memcpy 의 고속 복사 기능은 아쉽게도 사용할 수는 없군요.
​

문제풀이 해설로 들어가볼까요?

​

금번 문제는 ATM 키에 줄지어선 사람마다 돈을 찾는 시간이 다른데,

모든 사람의 대기시간 + 찾는시간을 가장 최소로 하도록 하도록 줄을 다시 세울때 소요되는 대기시간  + 찾는시간입니다.

예제로 주어진 데이터는 줄지어선 사람의 찾는 시간인데,

​

3 1 4 3 2 

​

대기시간 + 찾는 시간을 최소로 하려면 무조건 시간이 적은 순서로 정렬해야 합니다.

​

1 2 3 3 4

​

그래야 ( 찾는시간1분 ) + ( 대기시간 1분 + 찾는 시간 2분 ) + (대기시간 3분 + 찾는 시간 3분 ) + (대기시간 6분 + 찾는시간 3분 ) + ( 대기시간 9분 + 찾는시간 4분 ) 

= 총 32분으로 가장 적은 대기시간 + 찾는 시간이 되기 때문이지요.

​

결국 정렬해놓고 앞에서부터 대기시간 + 찾는시간을 모두 더해주면 됩니다.

​

데이터가 1000건 정도되니 버블소트로 간단히 처리하거나 

C++ 자체의 정렬 함수를 써도 되지만, 정렬문제가 앞으로도 잦을것 같아, 

크레이 나름대로 퀵소트 함수를 코딩하였습니다. 학습목적으로요 :)

​

퀵소트란 재귀 호출을 이용한 이분 정렬 알고리즘인데요.

아래와 같은 데이터가 주어질 때,

먼저 중앙점을 하나 잡고,

맨 앞에서부터 중앙점 이전까지는 숫자중 중앙점보다 큰 숫자는 중앙점의 오른쪽으로 보냅니다.

그러면 단계를 거듭할수록 이렇게 되지요.

이어서 중앙점 오른쪽에 숫자중에서는 중앙점보다 작은 숫자를 왼쪽으로 보냅니다.

이제 1차 작업이 끝났습니다.

중앙점을 기준으로 중앙점보다 작은 수는 왼쪽으로 큰 수는 오른쪽으로 이동되었지요?

​

이제 2차 작업에 들어갈 차례입니다.

중앙점을 기준으로 왼쪽 3개의 숫자를 새로 중앙점을 잡고 금방 그 작업을 다시 해주는 것입니다.

 

그러면 3개의 항목이 정렬되겠지요.

그 다음으로 또 다시 금방 오른쪽 목록을 중앙점을 잡고 정렬을 해줍니다.

6 8 9 10 7 5  ..

6 8 7 9 10 5
​
결과는 아래와 같겠지요?

다시 9 왼쪽의 4칸을 동일한 작업을 해 줍니다.

9 오른쪽은 1개 남았으니 더 이상 정렬할 필요가 없습니다.

이 과정을 모두 거치면,

최종 결과는 아래와 같습니다.

이런 방식을 퀵 소트라고 부르는데요.

핵심개념은 중앙점을 잡고 작은 수는 왼쪽으로 큰수는 오른쪽으로 보낸 다음,

중앙점을 기준으로 왼쪽범위를 다시 똑같은 작업을 해주고, 오른쪽도 똑같은 작업을 해주는 것입니다.

계속 그렇게 진행하다 왼쪽이나 오른쪽에 남은 숫자가 1개일 경우 더 이상 정렬할 필요가 없으므로 끝내는 방식입니다.

​

관련 소스 공개합니다.

주석 처리된 부분은 크레이가 고군분투한 흔적이지요 :) 

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 퀵소트(long) - 중앙 피벗
// 코딩 : 크레이
void QuickSort(long *arr, long n)
{
	// 피벗
	long mid=n/2;
	// 
	for(long i=0;i<n;++i)
	{
		// 큰 숫자는 오른쪽으로
		// 1 3 5 4 2 7
		//       m       i=2 m=3
		// 1 3 4 5 2 7
		//     m
		if(i<mid && arr[i]>arr[mid])
		{
			long save = arr[i];
			memcpy(arr+i, arr+i+1, sizeof(long) * (mid-i));
			arr[mid]=save;
			mid--; i--; continue;
		}
		// 작은 숫자는 왼쪽으로 
		// 1 3 4 5 2 7
		//     m          i=4, m=2
		// 1 3 2 4 5 7
		//       m
		if(mid<i && arr[mid]>arr[i])
		{
			long save = arr[i];
			for(long j=i-1;j>=mid;--j)
				arr[j+1]=arr[j];
			// 백준 사이트에서 역순 메모리 카피는 실행 안됨
			// memcpy(arr+mid+1, arr+mid, sizeof(long) * (i-mid));
			arr[mid]=save;
			mid++; continue;
		}
	}
	if(mid>1)QuickSort(arr, mid);
	if(mid<n-1)QuickSort(arr + mid + 1, n - mid - 1);
}

int main()
{
	int n;
	scanf("%d", &n);
	//n=1000;
	long *arr = new long[n];
	for(int i=0;i<n;++i)scanf("%ld", &arr[i]);
	QuickSort(arr, n);
	//sort(arr, arr+n);
	//for(int i=0;i<n;++i)printf("%ld ", arr[i]);
	long long subsum=0;
	long long sum=0;
	for(int i=0;i<n;++i)
	{
		subsum+=arr[i];
		sum+=subsum;
	}
	printf("%lld\n", sum);
	getchar(); getchar();
}