반응형
코드를 보기전에: 필자는 이 문제를 퀵정렬을 이용해 풀었다
다른 함수로 푸는걸 보고싶은 분들은 다른 블로그의 글을 보기 바란다.
출력:첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
첫번째 사람이 돈을 인출하는데 3분이 걸리고 두번째 사람은 인출하는데 2분이 걸린다고 하자.
그러면 첫번째 사람은 인출하는데 3분이 걸리고, 두번째 사람은 인출하는데 (3+2)분이 걸린다.
*첫번째 사람이 인출할때 뒤에서 기다리기 때문.
그래서 정렬을 이용해 오름차순으로 나열하면 최솟값을 구할수 있다.
코드를 보면서 하나하나 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <stdio.h>
int time[1001];
void quicksort(int* data, int start, int end)
{
if (start >= end) {
return;
}
int key = start;
int i = start + 1;
int j = end;
int temp;
while (i <= j) {
while (data[i] <= data[key]) {
i++;
}
while (data[j] >= data[key]&& j > start) {
j--;
}
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
}
else
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}quicksort(data, start, j - 1);
quicksort(data, j + 1, end);
}
|
cs |
우선 퀵정렬 함수의 코드다.
퀵정렬은 나중에 따로 한번 글을 올리겠다.
그 후 메인코드에서 사람의 수를 입력받은 다음, 반복문을 이용해 시간을 입력받았다.
여기서 동적메모리를 이용할까도 생각했었는데 배열이 하나밖에 없어서 그냥 호출했다.
그 후, 퀵 정렬을 이용해 입력받은 시간의 값을 오름차순으로 나열했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int main()
{
int num;
scanf("%d", &num);
for (int a = 0; a < num; a++)
{
scanf("%d", &time[a]);
}
quicksort(time, 0, num - 1);
int sum = 0;
for (int a = 0; a < num; a++)
{
sum += time[a] * (num - a);
}
printf("%d\n", sum);
}
|
cs |
사람이 5명 있다고 하면, 첫번째 사람이 돈을 인출할때는 4명이 기다린다.
그리고 두번째 사람이 돈을 인출할때 첫번째 사람은 집을 갔고, 나머지 3명은 뒤에서 기다린다.
이말은 첫번재 사람이 돈을 인출하는 시간이 5번 더해지고, 두번째 사람이 돈을 인출하는 시간은 4번 더해진다는 것이다
그래서 나는 반복문을 이용해 시간 X 사람수 - a를 했다.
반응형