[백준/BOJ] 13164. 행복 유치원 [Gold 5]

13164. 행복 유치원

문제출처 : https://www.acmicpc.net/problem/13164

code

#include <iostream>
#include <algorithm>
using namespace std;

int arr[300001], Diff[300001];
int main()
{
    ios::sync_with_stdio(false);

    int N, K, total;

    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    total = arr[N - 1] - arr[0];

    for (int i = 1; i < N; i++)
        Diff[i - 1] = arr[i] - arr[i - 1];

    sort(Diff, Diff + N - 1,greater<>());

    for (int i = 0; i < K - 1; i++)
        total -= Diff[i];

    cout << total;

    return 0;
}

문제풀고 너무 기분이 좋았던 문제중하나이다.

그냥 막들이대면 어렵지만, 잘 생각해서 풀어보자(내풀이가 정확한지는 모르겠다.)

입력은 오름차순으로 들어오기때문에 따로 정렬할 필요는 없고,

원생들의 배열을 수직선상에 놓고 생각해보자.

이렇게 되므로 총길이에서 조가 아닌 학생들만 빼주면 되는데,
1번방과 0번방의 키차이, 2번방과 1번방의 키차이, ...N-1번방과 N-2번방의 키차이배열을 구해서 내림차순으로 정렬한뒤, (총길이) - (0 ~ K-2번방 값) 을 빼주면 된다.