[백준] 13164번 행복유치원 (C++)

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

 

N이 30만이기 때문에 모든 경우를 확인할 수 없는 문제이다.

 

이런 각 숫자들의 차이에 따라 갈리는 문제들은 각 숫자들의 차이를 위주로 생각해야한다.

 

5 3
1 3 5 6 10

 

예제 문제를 예로 들어보자.

 

1 3 | 5 6 | 10

 

이렇게 막대를 새우면(그루핑하면) 정답이다. 이걸 어떻게 찾을 수 있을까? 이번엔 각 숫자들이 이웃한 숫자와 차이를 적어보자

 

2 2 1 4

 

이 숫자는 곧 각 사이에 막대를 두었을 때 없앨 수 있는 비용과 같다. 즉 여기서는 3개로 나눌 수 있으므로 막대는 2개 새울 수 있으므로, 4와 2 위치에 막대를 두면 정답을 찾을 수 있다.

 

1 | 3 5 6 | 10 이렇게 해도 정답은 3이므로 같은 값이면 막대를 어디에 두어도 상관없다.

 

그래서 문제는 정렬문제로 바뀐다.

 

각 자릿수의 차이를 구하여 배열을 만들고 정렬한다

 

1 2 2 4

 

그리고 마지막 막대를 새울 수 있는 가장 큰 M - 1개를 제외하고 모두 더한다. 

 

각 그룹을 위주로 생각하면 어려운 문제지만, 숫자들의 자리가 고정되어 있으므로 그룹위주가 아닌 옆그룹과의 차이가 최대인 것들만 빼내겠다는 어떻게보면 역발상을 떠올리기 어려운 문제이다. 다만 이러한 문제들은 한 번 완전히 이해하고 넘어가면 다음부터는 쉽게 떠올릴 수 있을 것이다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    int N, M; cin >> N >> M; 

    vector<int> tmp(N);

    for(int i = 0; i < N; i++){
        cin >> tmp[i];
    }

    vector<int> gap;

    for(int i = 1; i < N; i++){
        gap.push_back(tmp[i] - tmp[i - 1]);
    }

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

    int answer = 0; 

    for(int i = 0; i < gap.size() - (M - 1); i++) answer += gap[i];

    cout << answer << '\n';
}