[Algorithm] n개의 박스에서 k개를 골라 n명에서 공평하게 나눠주기

[문제] n개의 박스가 있고 각각 1,2,3,4,...n개의 사과가 들어 있다. 이때 k개의 박스를 골라서 n명에서 공평하게 나눠줄있는 k개의 박스 목록을 출력하세요.

 

답변 예시

(n,k)	apple box	answer	note
(3,3)	[1,2,3]	[1,2,3]	sum = 6 / 3 = 2
(3,1)	[1,2,3]	[3]	sum = 3 / 3 = 1
(3,2)	[1,2,3]	[1,2]	sum = 3 / 3 = 1
(11,2)	[1,2,3,4,5,6,7,8,9,10,11]	[1,10]	sum = 11 / 11 = 1

 

 

이문제 지난 포스트에 있는 C++ 미로찾기(graph traversal) 을 참조하면 조금더 쉽다.

미로찾기와 같이 2차원 그래프가 아니고 단방향 1차원이므로 tree 탐색의 문제다.

 

우선 중복없는 4개의 상자를 중복없는 조합으로 골라보자

void find_boxes(int n, int start, vector<int> & selected){
    cout << join_str(selected) << endl;

    for(int i=start;i<n;i++){
        selected.push_back(i+1);
        find_boxes(n, i+1, selected);
        selected.pop_back();
    }
}

void select_boxes(int n){
    vector<int> selected;
    find_boxes(n,0,selected);
}

void apple_box(){
    select_boxes(4);
}

// result
{}
{1}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,3}
{1,3,4}
{1,4}
{2}
{2,3}
{2,3,4}
{2,4}
{3}
{3,4}
{4}
{2}
{2,3}
{3}

 

오른쪽으로 상자하나씩 열어보고 마지막상자를 열어봤으면 이전 상자로 돌아가서 다음상자를 열어본다. 이름 트리로 그려보다 다음과 같다.

<>--------------|-------|---|
1-------|---|   2---|   3   4
2---|   3   4   3   4   4
3   4   4       4
4

 

결국은 깊이가 k이고 apple의 총합이 나머지가 남지 않으면 된다.

 

최종소스는 

bool find_boxes(int n, int k, int start, int sum, vector<int> & selected){
    if(selected.size() == k){
        if(sum % n == 0){
            return true;
        }
        return false;
    }

    for(int i=start;i<n;i++){
        selected.push_back(i+1);
        if(find_boxes(n, k, i+1, sum + (i+1), selected))
            return true;
        selected.pop_back();
    }
    return false;
}

void select_boxes(int n, int k){
    vector<int> selected;
    find_boxes(n, k, 0, 0, selected);
    cout << "result = " << join_str(selected) << endl;
}

int main(int argc, char * argv[]){
    select_boxes(4, 2);
    return 0;
}