[11399번] ATM (Greedy Algorithm)

문제 출처 : 

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

알고리즘 분석 :

Greedy Algorithm(탐욕 알고리즘)이 녹아있는 문제이다.

탐욕 알고리즘이란? 가장 가까이에 있는것만 보다가 손해를 보는 것이다.

예를 들어 거스름 돈을 12, 8, 5, 3, 1을 줄 수 있을 때

15의 거스름 돈을 주어야 한다면 12, 3 두개를 이용하여 가장 최소의 동전으로 거스름 돈을 줄 수 있다.

하지만 16의 거스름 돈을 주어야 한다면 눈앞에 보이는 가장 큰 것을 이용한다면 12 3 1을 생각하지만, 

8 8 로 해결 할 수 있는 것이다. 이것이 Greedy Algorithm(탐욕 알고리즘)이다.

이 문제 또한 최소의 값을 원하고 있으니 탐욕 알고리즘을 통해 풀어낸다면 아래의 소스코드와 같이 해결 할 수 있을 것이다.

소스 코드 : 

#include <stdio.h>
 
int arr[1001];
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
 
 
int main()
{
    int n, k, i, j, tmp;
    int cnt = 0;
    int temp[1001] = { 0, };
    int ans = 0;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
 
    QuickSort(arr, 0, n - 1); // 퀵 정렬로 값을 정렬한다.
 
 
    for (i = 1; i <= n; i++)
    {
        temp[i] = temp[i - 1] + arr[i-1]; // 누적하여 더한 값을 배열에 저장한다.
    }
 
    for (i = 1; i <= n; i++)
    {
        ans = ans + temp[i]; // 누적된 배열 값들을 모두 ans에 더한다.
    }
 
    printf("%d",ans);
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>