[Algorithm] 백준 - 행복 유치원 (13164번)

문제

[백준] 행복 유치원

13164번: 행복 유치원

 

사용 알고리즘

- 그리디 (Greedy)

해결방법

• 원생 사이의 키 차이가 비용일 때, 비용이 최소값이 되게 하려면 서로 인접한 원생들의 키 차이를 봤을 때, 비용이 가장 큰 사이부터 갈르면 된다.
  • 예를 들어, 문제 예제 1번의 경우
    원생의 키 : 1 3 5 6 10
    키차이(거리) : (2)(2)(1)(4)
    
    • 총 3그룹으로 만드로 싶다면, 원생 사이를 2번 가르면 되는데, 이 때 키차이가 큰 구간부터 가른다고 생각하면 된다.
      > 1 | 3 5 6 | 10
      > 1 3 | 5 6 | 10
      이렇게 두가지 경우가 나오는데, 두 경우 모두 비용은 3으로 같다.
• 키 차이 벡터를 만들고, N개의 그룹을 만들고 싶다면 N-1번 커팅(remove)해서 남은 차이를 다 합한게 총 비용이 된다.

소스코드

사용언어 : c++

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

using namespace std;

vector<int> height;
vector<int> dist;

int main()
{
    int N, K, res=0;

    cin >> N >> K;

    int input = 0;
    for (int i=0; i<N; i++) {
        cin >> input;
        if (i > 0) dist.push_back(input - height.back()); //원생 사이의 키 차이 벡터

        height.push_back(input);
    }

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

    for (int i=0; i<K-1; i++) {
        dist.pop_back();
    }

    res = accumulate(dist.begin(), dist.end(), 0);
    cout << res;

    return 0;
}

accumulate(v.begin(), v.end(), T init)

* #include <numeric> 헤더 선언을 통해 사용할 수 있다.

* 벡터의 합을 구할 수 있는 함수

* 세 번째 인자인 init는 합의 초기값을 의미하며, accumulate의 반환값이 init의 타입을 따라간다.

#include <numeric>

sum = accumulate(v.begin(), v.end(), 0); // 소수점 결과가 필요하면 0을 double(0)으로 해도 된다

 

한줄평

원생들의 키 벡터를 만든 후, 해당 벡터를 for문 돌면서 자르는 식으로 풀었는데 잘 안됐다. 이 문제는 키 차이 벡터를 생성해서 볼 줄 아는게 포인트(킥!)