[BaekJoon/백준] 11399번 그리디 알고리즘

그리디 알고리즘은 동적계획법처럼 dp배열을 다룰 필요 없다(점화식을 세우지 않는다). 모든경우의 수를 찾아볼 필요 없기 때문.

자세한 내용은 블로그 내의 동적계획법vs그리디알고리즘 글 참고.

---

 

 

ATM 문제.

설명글을 읽으면 어느정도 느낌이 온다. 주어진 수를 오름차순으로 정렬한 뒤 누적으로 더해주면 해결되었다.

오름차순 정렬은 오픈 라이브러리인 stdlib.h의 qsort함수를 사용했다. 비교함수는 기본적인 형태로 진행.

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

int N;
int P[1000];

int count = 0;

int compar(int *a, int *b) {
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
}
int main() {
    
    int i;
    scanf("%d", &N);
    
    for(i = 0; i < N; i++ ) {
        scanf("%d",&P[i]);
    }
    
    qsort(P, N, sizeof(int), compar);
    
    count = P[0];
    
    for(i = 1; i < N; i++) {
        P[i] += P[i - 1];
        count += P[i];
    }
    printf("%d", count);
}