2021 KAKAO INTERNSHIP [시험장 나누기] [C++]

https://programmers.co.kr/learn/courses/30/lessons/81305

코딩테스트 연습 - 시험장 나누기

---

문제 요약

시험장이 트리의 형태로 주어지고 각각 시험장에 몇 명에 인원들이 있는지 입력으로 주어진다

시험장을 k개의 그룹으로 묶은 후 k개의 그룹 중 가장 인원이 많은 그룹의 인원수의 최솟값을 구하라.

 

---

나의 풀이

이 문제를 처음 보자마자 이 문제가 생각났다.

사실 이 문제와 그림이 비슷하고 트리 자료구조로 정보가 주어진다는 점 빼고는 아예 다른 문제이다

저 문제가 생각났기 때문에 트리 DP로 생각을 하였지만

이전 상태의 값을 이용하여 다음 상태의 값을 도출해내는 DP의 로직을 여러 가지 그룹이 생길 수 있는 상황에서 짤 수 없을 것 같다는 생각이 들어 다른 방식으로 생각했다.

 

문제를 보면  그룹의 인원수의 최댓값은 특정 x 값이 될 수도 있고 안될 수도 있을 것이다

이 특정 x 값 이내에 인원수만 존재하도록 그룹을 만들어가며 k개 넘게 그룹이 생겼는지만 확인해주면 가능 여부를 파악할 수 있다.

여기서 가능불가능를 판단하는 로직을 이용하여 이분 탐색법을 사용해주면 이문제는 제한시간 안에 해결할 수 있다.

 

나의 경우 link 로 주어진 배열을 단방향 연결 리스트로 바꿔주었고

0 ~ n 까지의 노드 중 어떤 것을 root 노드로 잡아도 결과에 영향을 주지 않기 때문에 0번 노드를 root로 잡았다.

 

이분 탐색 구현 시 주의할 점 

• 이분 탐색의 left 값은 모든 시험장의 인원 수중 최댓값이 와야 한다.
  (최댓값보다 작은 값을 mid로 설정하면 해당 시험장을 그룹핑할 수 없게 된다)
• 이분 탐색의 right 값은 모든 시험장의 인원수 합이 와야 한다.

 

이 문제도 사실 미로 탈출 문제와 같이 결국은 특정 케이스에 대한 상황을 생각할 때 직접 시뮬레이션을 해봐야 답을 알 수 있는 종류의 문제였다.

미로 탈출 문제에서는 다 해보는 방법 구현할 때 공간을 기억하기 위해서 어떻게 자료구조를 정리하는지의 문제였다면

이 시험장 나누기 문제에서는 시간을 줄이기 위해 모든 상황을 시뮬레이션하지 않고 이분 탐색의 개념을 이용하여 확실히 아닌 것은 시뮬레이션하지 않으면서 답의 범위를 줄이는 방법을 생각해야 하는 문제였던 것 같다.

---

소스코드

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
vector<int> people;
vi e[10001];
vi edir[10001];
bool chk[10001];
int cnt=0,root;
void go(int idx){
    chk[idx]=true;
    for(int next : e[idx]){
        if(!chk[next]){
            edir[idx].push_back(next);
            go(next);
        }
    }
}
pii getGroupCount(int idx,int maxCnt){
    // first : 개별의 갯수 , second : 군집의 갯수
    pii tmp = {people[idx],0};
    chk[idx]=true;

    vpii childs;
    for(auto next : edir[idx]){
        if(!chk[next]){
            childs.push_back(getGroupCount(next,maxCnt));
        }
    }

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

    for(auto child: childs){
        if(tmp.first + child.first <= maxCnt){
            tmp.first += child.first;
        }else{
            tmp.second += 1;
        }
        tmp.second += child.second;
    }
    return tmp;
}
int solution(int k, vector<int> num, vector<vector<int>> links) {

    memset(chk,false,sizeof(chk));
    int n = num.size(),minVal=0,sum=0;
    people=num;

    for(int i=0;i<n;i++){
        sum+=num[i];
        minVal = max(minVal,num[i]);
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            int from  = i;
            int to  = links[i][j];
            if(to!=-1){
                e[from].push_back(to);
                e[to].push_back(from);
            }
        }
    }

    go(0);

    int l=minVal,r=sum,mid,ans=INF;
    while(l<=r){
        memset(chk,false,sizeof(chk));
        mid=(l+r)/2;
        auto result = getGroupCount(0,mid);
        int need = (result.first > 0 ? result.second+1 : result.second);
        if( k >= need){
            ans = min(ans , mid);
            r = mid-1;
        }else if(k<need){
            l = mid+1;
        }
    }
    return ans;
}