백준#11399-ATM

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

11399번: ATM

 

그리디 알고리즘으로 분류된 11399번 ATM 문제 입니다.

 

마지막 사람이 완료한 시간을 구하는 것이 아닌 모든 사람의 걸린 시간 합을 구하는 것입니다.

 

1, 2, 3 이렇게 세 사람이 있을 때

 1번 사람은 1분, 2번 사람은 3분, 3번 사람은 6분에 완료하게 됩니다.

이 세사람의 걸린 시간을 모두 더해 10이 결과 값이 되는데

 

3, 2, 1 이렇게 줄을 섰다고 할 경우

1번 사람은 3분, 2번 사람은 5분, 3번 사람은 6분에 끝나며 이 합은 14분이 됩니다.

 

앞에 시간이 오래 걸리는 사람이 있을 경우 뒷사람에 더해지면서 전체 시간이 늘어나는 것입니다.

최종적으로 N명의 사람이 있고 N개의 배열에 각 시간이 주어진다면 cost[0] * N + cost[1] * (N-1)...

결국 걸린 시간이 적은 순으로 줄을 세우면 가장 적은 시간이 나오게 됩니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _11399
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            List<int> costList = new List<int>();
            string[] strCostArray = Console.ReadLine().Split(' ');
            foreach (string cost in strCostArray)
                costList.Add(int.Parse(cost));
 
            costList.Sort();
            int sum = 0;
            for(int i = 0; i < costList.Count; i++)
            {
                sum += (costList.Count - i) * costList[i];
            }
            Console.WriteLine(sum);
        }
    }
}

이것이 최종 소스코드 되겠습니다.