[9882번] Balanced Teams

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

이 문제는 재귀속 재귀를 4번 돌리면 되는 문제이다.

12명 중 3명을 고르고, 9명중 3명을 고르고, 6명중 3명을 고르고, 3명중 3명을 고르면

12C3 * 9C3 * 6C3 * 3C3이기에 4중 재귀여도 문제 해결이 가능하다.

우선 cnt == 3 즉, 3개를 고르면 ret라는 구조체 배열에 담아주고 구조체 배열이 4개가 되면 그때 최소,최댓값의 차를 구하며 계속 진행한다.

아래에 두가지 코드가 있는데 2번째 코드는 next_permutation을 조합으로 바꾸는 방법을 설명해두었다.

STL로 해결하면 훨씬 더 코드가 간결해진다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
struct INFO {
    int num[3];
};
 
INFO ret[4];
 
int arr[12];
bool visit[12];
 
int ans = 987654321;
void combination(int idx, int cnt, INFO info, int retCnt) {
    if (retCnt == 4) {
        int minVal = 987654231;
        int maxVal = -1;
 
        for (int i = 0; i < 4; i++) {
            int val = 0;
            for (int j = 0; j < 3; j++)
                val += ret[i].num[j];
 
            minVal = min(minVal, val);
            maxVal = max(maxVal, val);
        }
 
        ans = min(ans, maxVal - minVal);
 
        return;
    }
    if (cnt == 3){
        ret[retCnt] = info;
        info.num[0] = info.num[1] = info.num[2] = 0;
        combination(0, 0, info, retCnt + 1);
        return;
    }
 
    for (int i = idx; i < 12; i++) {
        if (!visit[i]) {
            visit[i] = true;
            info.num[cnt] = arr[i];
            combination(i + 1, cnt + 1, info, retCnt);
            info.num[cnt] = 0;
            visit[i] = false;
        }
    }
}
int main() {
    for (int i = 0; i < 12; i++)
        scanf("%d", &arr[i]);
 
    INFO info = { 0, };
    combination(0, 0, info, 0);
 
    printf("%d", ans);
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

#include <bits/stdc++.h>
using namespace std;
int perm[] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3};
int N, a[15], ans;
 
int main(){
    N = 12;
    for(int i = 0; i < N; i++)
        scanf("%d", a + i);
    ans = 1e9;
    do{
        int s[4] = {0,};
        int mn = 1e9, mx = -1e9;
        for(int i = 0; i < N; i++)
            s[perm[i]] += a[i];
        for(int i = 0; i < 4; i++){
            mx = max(mx, s[i]);
            mn = min(mn, s[i]); 
        }
        ans = min(ans, mx - mn);
    }while(next_permutation(perm, perm + 12));
    printf("%d\n", ans);
    return 0;
}