[백준] 11399번 문제풀이

문제 : www.acmicpc.net/problem/11399 

11399번: ATM

풀이방법

1. 시간을 기준으로 Sorting. (나는 mergeSort를 이용함)

2. 앞에서 부터, 시간을 더함(sum1). 시간을 더한 값을 또 더함(sum2) - 아래코드 참고

int sum1, sum2;
sum1 = sum2 = 0;
for (int i = 0; i < n; i++)
{
	sum1 += arr[i];
	sum2 += sum1;
}

 

 

코드 :

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int* mergeSort(int arr[], int left, int right);
int* merge(int arr[], int left, int mid, int right);

int main(void)
{
	int n;
	scanf("%d", &n);

	int arr[1000];
	for (int i = 0; i < n; i++)
	{
		scanf(" %d", &arr[i]);
	}
	mergeSort(arr, 0, n - 1);

	int sum1, sum2;
	sum1 = sum2 = 0;
	for (int i = 0; i < n; i++)
	{
		sum1 += arr[i];
		sum2 += sum1;
	}

	printf("%d", sum2);
	return 0;
}

int* mergeSort(int arr[], int left, int right)
{
	if (left == right) return arr;
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
	return arr;
}

int* merge(int arr[], int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;
	int temp[1000];

	while (i <= mid && j <= right)
	{
		if (arr[i] > arr[j])
		{
			temp[k++] = arr[j++];
		}
		else
		{
			temp[k++] = arr[i++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
	return arr;
}

 

걸린시간 : 1시간 17분 (알고리즘 : 17분, 디버깅 및 구현 : 1시간 (mergeSort구현 59분))

 

MergeSort를 정확하게 손에 익혀놓았다면 훨씬 빠르게 구현이 가능했었을 텐데.. 아쉽다.

몇 번 연습해봐야겠다.