백준 2295 - 세 수의 합

 

 

문제 설명

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 정렬된 원생들을 K개의 그룹으로 묶고 각 그룹의 가장 큰 원생과 가장 작은 원생의 키차이가 비용이라고 할 때, 최소 비용을 구해야 한다.

 

해당 문제는 생각의 전환이 중요한 문제이다.

핵심은 가장 큰 키와 가장 작은 키의 차이는 중간 원생들의 키와는 상관없어 보이지만 사실을 그렇지 않다는 것이다.

무슨 말이냐면 가장 큰 키와 가장 작은 키의 차이는 바로 옆사람과의 차이의 합과 같다.

예를 들어 보자.

5 3
1 3 5 6 10

1~6까지 그룹으로 묶었다고 가정해 보자.

이 그룹의 비용은 $6 - 1 = 5 $이다.

이는 $(3-1) + (5-3) + (6-5) = 5$와 같다.

 

그럼 최소 비용을 만드는 방법을 생각해보자.

결국 모든 아이들을 포함시켜야 하기 때문에 모든 구간이 포함된다.

단, 한 가지 제외할 수 있는 경우가 있다.

자기 자신만 그룹에 포함된 경우는 최대-최소가 0이기 때문에 구간을 제외시킬 수 있다.

즉, 바로 옆사람과의 차이를 모두 구하고 정렬한 뒤, K-1개의 가장 큰 구간을 제외하면 최소 비용을 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, K;
vector<int> kids;
vector<int> diff;

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N >> K;

    kids.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> kids[i];
        if (i == 0) continue;
        diff.push_back(kids[i] - kids[i - 1]);
    }

    sort(diff.begin(), diff.end());

    long long ans = 0;
    for (int i = 0; i < N - K; i++)
    {
        ans += diff[i];
    }

    cout << ans;

    return 0;
}

---