백준 11399-ATM(C언어)

문제 링크 : 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)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

 

 

출력

 

 

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

 

 

예제 입력

 

 

5
3 1 4 3 2

 

 

 

 

예제 출력

 

 

32

 

 

 

 

해설

 

 

 

시간의 합의 최솟값을 구하란다. 문제를 읽어보면 알겠지만

"만약 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2라면 줄을 [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분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다."이곳을 보면 시간이 적게 걸리는 사람부터 줄을 서야 최소값이 나온다는 것을 알 수 있다.

그 이유는 첫번째 사람은 자기가 걸리는 시간만 기다리면 되지만 두 번째 사람은 자기가 걸리는 시간과 첫 번째 사람이 걸리는 시간을 모두 기다려야 하고 세 번째 사람은 첫째, 둘째, 셋째(자신)가 걸리는 시간을 모두 기다려야 하는, 즉 기다리는 시간이 누적되기 때문이다. 

 

걸리는 시간(오름차순 정렬)	기다리는 시간
1	1
2	1+2
3	1+2+3
3	1+2+3+3
4	1+2+3+3+4
총 기다리는 시간->	1+3+6+9+13=32

 

 

 

이를 토대로 문제를 해결하려면 첫째로 시간이 짧은 순서를 구할 수 있어야 하고 누적합을 구할 수 있어야 한다.

 

일단 시간이 짧은 사람순서대로 정렬해야 하는데 사람 수의 조건은 1~1000명으로 최대 1000명이다. 이 처럼 정렬해야 할 수가 적은 경우에는 카운팅 정렬(계수 정렬)이 효과적이다. 카운팅 정렬은 버블 정렬이나 선택 정렬처럼 먼저 배열에 수를 저장한 뒤 수들을 비교하여 위치를 바꾸는 것이 아닌 아예 처음 수를 입력받을 때부터 정렬하는 방법이다. 어떻게 하는 것이냐면 예를 들어 수 10개를 3,5,6,2,2,1,9,6,7,6 이렇게 입력받았다 하자. 가장 큰 수는 9이니 최소 9개 항목의 배열이 필요하다. 일단 이 배열의 모든 항목을 0으로 초기화하고 숫자 x를 입력받으면 배열의 x번째 항목을 1 더한다. 이는 숫자 x가 1개 늘어났다는 뜻이다. 이렇게 하여 위에 있는 수 10개를 모두 넣으면 배열은 [1,2,1,0,1,3,1,0,1] 이렇게 된다. 1은 1개, 2는 2개, 3은 1개, 4는 0개..... 9는 1개 있다는 뜻이다. 이렇게 하면 정렬이 완료되었다.

 

 

이제 두 번째 누적합을 구해야 한다. 바로 위 10개 숫자를 오름차순으로 나타내면 1,2,2,3,5,6,6,6,7,9이다.

이렇게 시간이 적게 걸리는 사람부터 줄을 서야 누적합이 최솟값이 나온다. 1번째 사람이 걸리는 시간인 1분은 

1번째 사람뿐만 아니라 마지막 사람까지 총 10명이 기다려야 하는 시간이고 2번째 사람이 걸리는 시간인 2분은 

2~10번째 사람(9명) 모두 기다려야하는 시간이고 3번째 사람이 걸리는 시간인 2분은 3~10번째 사람(8명) 모두 기다려야하는 시간이기 때문이다. 그래서 시간이 적게 걸리는 사람부터 줄을 서야 하는 것이다. 

누적합-> 첫 번째 사람이 걸리는 시간인(1)*기다려야 되는 사람 수(10)+두 번째 사람 걸리는 시간(2)*기다려야 되는 사람 수(9)+2*8+3*7+5*6+6*5+6*4+6*3+7*2+9*1이다.

 

 

 

 

코드

#include<stdio.h>
int main(void)
{
	int n,a[1000]={0},k,sum=0;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d", &k);
		a[k-1]++;
	}
	k=0;
	while(n>0)
	{
			if(a[k]>=1)
			{
				sum+=n*(k+1);
				a[k]--;
				n--;
			}
			else
				k++;
	}
	printf("%d", sum);
}

전체적인 원리를 설명하자면 사람 수와 각각의 걸리는 시간을 입력받고 입력받은 시간을 카운팅 정렬을 이용해 정렬한다. 카운팅 정렬이 되어있는 배열의 앞에서 부터시작해 0이 아닌 부분이 나오면 (걸리는 시간*기다려야 되는 사람 수)를 더한 후 현재 배열 요소와 n(기다려야 하는 사람 수)에 1을 빼준다. 현재 배열 요소가 0이 될 때까지 반복한 후 0이 되면 다음 배열 요소로 넘어간다. 이렇게 모든 합을 다 더하면 답이다.

 

6행의 for문은 카운팅 정렬을 하는 부분이고,  12행의 while문은 누적합을 구하는 부분인데 16행에서 sum은 누적합이고

n은 기다려야 하는 사람 수, (k+1)은 걸리는 시간이다. 참고로 배열의 인덱스는 0부터 시작하기에 k가 아닌 k+1이라 하였다. 17행의 a[k]--로인해 특정 시간이 걸리는 인원이 명 몇 인지 알아내 누적합을 구하는데 필요하고, 18행에서 n--를 하는 이유는 기다리는 줄이 줄어들수록 기다려야 하는 사람 수도 줄기 때문에 한 것이다. 

21행에서 k++는 a[k]의 값이 0이면 다음 요소로 넘어가기 위해 한 것이다.