[C#] 백준 30088번 문제풀이

문제번호: 30088

문제명: 공포의 면담

문제링크: https://www.acmicpc.net/problem/30088

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘의 문제는 공포의 면담이라는 문제입니다.

이 문제는 그리디 알고리즘을 활용하여 모든 부서의 퇴근시간의 합을 구하는 문제입니다.

핵심 아이디어는 각 부서별 퇴근시간의 합이 가장 짧은 시간을 앞쪽 리스트에 배치시켜(정렬) 총 퇴근시간의 합을 최소화시키는 것 입니다.

다음은 정답코드입니다.

 

static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    List<int> list = new List<int>();

    for (int i = 0; i < N; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        int n = input[0];

        int[] arr = new int[n];

        for (int j = 0; j < n; j++)
            arr[j] = input[j + 1];

        Array.Sort(arr);

        int sum = 0;
        foreach (int t in arr)
            sum += t;

        list.Add(sum);
    }

    list.Sort();

    long answer = 0;
    long prefix = 0;

    foreach (int v in list)
    {
        prefix += v;
        answer += prefix;
    }

    sw.WriteLine(answer);
}