[C언어] 백준 11399번 ATM

링크

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

11399번: ATM

 

 

 

 

 

문제

---

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력

---

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 \(P_i\)가 주어진다. (1 ≤ \(P_i\) ≤ 1,000)

 

 

 

출력

---

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

 

 

예제 입력 1

---

5
3 1 4 3 2

 

예제 출력 1

---

32

 

 

 

 

아이디어 스케치

---

- 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제로 각 사람이 기다리는 시간의 누적합의 최소를 구하는 문제이다.

- 따라서 누적합을 이용해야 한다.

- 모든 사람이 가장 적은 시간내에 돈을 인출하려면 인출하는데 걸리는 시간이 적은 순서대로 오름차순으로 정렬해야 한다.

- 앞의 사람이 인출하는 동안 뒤의 사람들도 똑같이 시간이 흐르고 있기 때문에 오름차순 정렬 후 각 사람이 총 소비한 시간을 구하기 위해서는 누적 합을 이용해야 한다. 예를들어 1 2 3이 있으면 앞사람은 1분 두번째 사람은 1+2분, 세번째 사람은 1+2+3분이 소비된다. 즉 누적 합만큼의 시간이 소비된다.

- 누적 합을 구한 후, 구한 누적합을 더하면 인출하는데 필요한 시간의 합을 구할 수 있다.

 

 

 

 

 

코드 분할 설명

---

arr = (int*)calloc(N, sizeof(int));
	result = (int*)calloc(N, sizeof(int));

	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	qsort(arr, N, sizeof(arr[0]), compare);		//퀵 정렬

 

- N을 입력받은 후 N크기 만큼의 배열 2개를 동적할당한다.
- 걸리는 시간을 입력받은 후 내림차순으로 정렬한다.

 

 

 

 

int compare(const void* first, const void* second)
{
	int a = *(int*)first;
	int b = *(int*)second;

	if (a > b)
		return 1;		// 오름차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

 

- 퀵 정렬 인자로 들어가는 비교함수로 오름차순 정렬을 뜻한다.

 

 

 

for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++)
			result[i] += arr[j];				//누적합 저장
	}

 

- 오름차순 정렬한 배열의 누적 합을 구해 result배열에 저장한다.

 

 

 

 

for (int i = 0; i < N; i++)
		sum += result[i];

 

- 구한 누적 합의 합을 구한다.

 

 

 

 

 

전체 코드

---

#include <stdio.h>
#include <stdlib.h>

int compare(const void* first, const void* second)
{
	int a = *(int*)first;
	int b = *(int*)second;

	if (a > b)
		return 1;		// 오름차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

int main()
{
	int N;
	int* arr;		// 입력 받을 배열
	int* result;	// 누적합을 구해 저장할 배열
	int sum = 0;

	scanf("%d", &N);

	arr = (int*)calloc(N, sizeof(int));
	result = (int*)calloc(N, sizeof(int));

	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	qsort(arr, N, sizeof(arr[0]), compare);		//퀵 정렬

	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++)
			result[i] += arr[j];				//누적합 저장
	}
	for (int i = 0; i < N; i++)
		sum += result[i];

	printf("%d", sum);

	free(arr);
	free(result);

	return 0;


}

 

 

 

 

 

 

 

제출 결과

---