[백준] 13164 - 행복 유치원

1. 문제

13164번: 행복 유치원

2. 개요

유치원에 N명의 학생들이 있다.

이 학생들을 K개의 조로 나누고, 조별로 티셔츠를 맞추려고 한다.

티셔츠를 맞추는 데 드는 비용은 각 조의 (최장신 - 최단신) 만큼 든다.

학생들의 키가 오름차순으로 주어졌을 때 최소 비용을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

학생들의 키가 오름차순으로 주어졌기 때문에 각 조의 비용은 인접한 학생과의 키차이의 총합이 된다. K개의 조를 만들게 되면 인접한 학생 사이의 키 차이가 사용되지 않는 부분이 K-1개 나오게 된다.

이를 이용하여 인접한 학생들 간의 키의 총합에서 그 차이가 가장 큰 순서대로 K-1개를 빼주게 되면 답을 구할 수 있다.

학생들을 탐색하면서 인접한 학생과의 키 차이를 구하여 답을 그만큼 늘려주며 리스트에 저장한다.

모든 키 차이를 저장한 뒤, 내림차순으로 정렬한다.

키 차이 리스트를 K-1번째 인덱스까지 탐색하며 답에서 그 값만큼 빼준다.

탐색이 완료되었다면 답을 출력한다.

3-2. Python

import sys

N, K = map(int, sys.stdin.readline().split())

heights = list(map(int, sys.stdin.readline().split()))

hdiffs = []
answer = 0

for i in range(1, N):
    hdiffs.append(heights[i] - heights[i-1])
    answer += heights[i] - heights[i-1]

hdiffs.sort(reverse=True)

for i in range(K-1):
    answer -= hdiffs[i]

print(answer)

3-3. C#

namespace boj_13164
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]);

            int answer = 0;
            int[] heights = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            int[] hdiffs = new int[N - 1];

            for (int i = 1; i < N; i++)
            {
                hdiffs[i - 1] = heights[i] - heights[i - 1];
                answer += heights[i] - heights[i - 1];
            }

            Array.Sort(hdiffs, (a, b) => b.CompareTo(a));

            for (int i = 0; i < K - 1; i++)
                answer -= hdiffs[i];

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}