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

13164. 행복유치원

13164번: 행복 유치원

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

어이가 없이 어려웠던 문제... 문제 자체도 어려웠지만 유치원생의 최대 키가 10^9라는 것도 황당했다...

 

처음엔 도대체 어떻게 접근해야할지 몰라서 나의 그리디 문제 빅데이터를 사용해서 처음부터 차근차근 조를 정해가는 방법을 떠올렸다.

 

하지만... 아무리 생각해도 아무 정보도 없는 채로 처음부터 수를 탐색하는 건... 시간도 시간이고, 답도 나오지 않을 것 같았다.

원생의 키 차이는 절대적이지 않고, 상대적이므로 1과 3이 묶일 수도 있지만, 1의 키와 100이 묶일 가능성도 없지 않다.

 

이 생각을 기반으로 알고리즘을 생각해봤다.

 

알고리즘 설계

1. 인접한 학생들의 키 차이와 인덱스를 배열에 저장한다.

array (diff, index)=>
[{2-1, 0}, {3-2, 1}, {100-3, 2}, {101-100, 3}...]

[{1, 0}, {1, 1}, {97, 2}, {1, 3}, {1, 4}, {198, 5}, {1, 6}, {1, 7}]

차만 배열에 저장하면...

input =>
9 3
1 2 3 100 101 102 300 301 302

 

 

2. 키 차이를 기준으로 내림차순으로 정렬한다.

[{198, 5}, {97, 2}, {1, 7}, ...]

 

3. 배열의 0~K(그룹의 수 - 1)까지를 인덱스를 기준으로 다시 오름차순 정렬한다.

[{97, 2}, {198, 5}]

 

4. 배열의 인덱스 순으로 조를 끊어주고, 최단신과 최장신의 차를 구한다.

(3-1) + (102-100) + (302-300)
= 2 + 2 + 2
= 6

1 2 3 100 101 102 300 301 302

* 2번째 인덱스 => 3과 100 사이
* 5번째 인덱스 => 102과 300 사이

1 2 3 | 100 101 102 | 300 301 302

이렇게 완벽하게 나누어 진다!!

 

 

코드

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

struct diff
{
 int index;
 int diff;
};

typedef long long int lli;

int arr[300000];
vector<struct diff> diff;

int main()
{
 int len, group, startIdx = 0;
 long long int answer = 0;
 cin >> len >> group;

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

 // 숫자 사이의 차(구조체)를 모두 배열에 넣어준다
 for (int i = 0; i < len - 1; i++)
     diff.push_back({ i, arr[i + 1] - arr[i] });

 if (!diff.empty())
 {
     // 차를 내림차순으로 정렬한다
     sort(diff.begin(), diff.end(), [](auto a, auto b) {return (a.diff > b.diff); });

     // 쓸 부분 말고 제거
     if (len != group)
         diff.erase(diff.begin() + group - 1, diff.end());

     // 정렬한 차이를 인덱스 순으로 오름차순 정렬한다
     sort(diff.begin(), diff.end(), [](auto a, auto b) {return (a.index < b.index); });
 }

 // 마지막 인덱스도 넣어준다.
 // 반복문 계산을 위해
 diff.push_back({ len - 1,0 });

 for (int i = 0; i < diff.size(); i++)
 {
     // 0부터 a1, a1+1부터 a2, a2+1부터 a3...
     // 그룹으로 묶어 최댓값과 최솟값의 합을 저장한다.
     answer += (lli)arr[diff[i].index] - arr[startIdx];
     startIdx = diff[i].index + 1;
 }

 cout << answer;
}

조금 가독성 없고 길긴 하지만...

 

나름 구현은 잘 해낸 것 같다. 엄청 어렵고... 생각도 필요한 문제였지만, 찬찬히 생각해서 답을 도출해낸 게 뿌듯하다. 나중에 다시 풀어봐야겠다.