백준 11399번은 문제 구분은 그리디 알고리즘, 즉 탐욕 알고리즘으로 되어있다. 내가 최대한 아는대로 설명해보려고 한다.
탐욕 알고리즘(Greedy Algorithm)은 선택했을 때의 최적의 상황만 찾는 알고리즘을 뜻한다. 그 말은, 이 알고리즘은 최적해를 찾는 방법 중 하나이지만, 언제나 최적해를 찾아주는건 아니라는 것이다.
총 5명의 사람이 있고, 각각 번호가 1 ~ 5번까지 붙어있고, 사람이 돈을 뽑는데 걸리는 시간을 a ~ e분이라고 하자. 만약 [1, 2, 3, 4, 5] 순으로 뽑게 된다면, 전체 걸리는 시간은 다음과 같다:
(5 x a) + (4 x b) + (3 x c) + (2 x d) + (1 x e) = Time
식만 보았을때는, a가 커지는 폭이 클 수록 Time이 커지는 폭이 커질 것을 예상할 수 있고, 그로 인해 맨 앞 사람이 돈을 빨리 뽑을수록 시간이 줄어든다는 것을 알 수 있다. 그러므로, 주어진 시간을 정렬 알고리즘을 이용해 정렬한 후 계산해주면 되겠다.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int num;
scanf("%d", &num);
int *time = (int*)malloc(sizeof(int) * num);
int *time_plus = (int*)malloc(sizeof(int) * num);
for (int i = 0; i < num; i++) {
scanf("%d", &time[i]);
time_plus[i] = 0;
}
for (int i = 0; i < num; i++) {
for (int j = i + 1; j < num; j++) {
if (time[i] > time[j]) {
int temp = time[i];
time[i] = time[j];
time[j] = temp;
}
}
}
time_plus[0] = time[0];
for (int i = 1; i < num; i++) {
for (int j = 0; j <= i; j++) {
time_plus[i] += time[j];
}
}
int sum = 0;
for (int i = 0; i < num; i++) {
sum += time_plus[i];
}
printf("%d\n", sum);
free(time);
free(time_plus);
return 0;
}탐욕 알고리즘이 최적해인지 아닌지 구별해줄 수 있는 공간을 메트로이드 공간 구조(Matroid Structure)라고 한다. 다만, 한 문제의 공간이 메트로이드 구조를 이루면 탐욕 알고리즘으로 최적해를 구해낼 수 있지만, 탐욕 알고리즘이라고 무조건 메트로이드 구조를 이루는 것은 아니라고 한다.
