[SWEA] 4747 사막에서 만난 지니

출처: SWEA

Approach

문제를 맞추려면 조건 中에서

3 ≤ N ≤ 2000 와 1 ≤ V ≤ 10000 조건을 만족해야 한다.

 

개수 상관없이 3명의 아이들에게 동일한 값어치를 분배할 때, 

각자 받은 물건의 값어치는 배낭에 있었던 물건들의 {총 값어치 ÷ 3} 이다.

ex) {1, 2, 3, 4, 5} → 1 + 2 + 3 + 4 + 5 → 15 ÷ 3  = 5 (=아이들이 받은 물건의 값어치)

즉, 평균(avg)에 해당하는 것을 알 수 있다.

 

다음 고려해야 할 부분은 어떻게 분배해야 할 것인지이다.

Input Data에서 한 사람당 받은 물건의 총 값어치를 알 수 있기에

1번에게 물건 배정 → 2번에게 물건 배정까지 한다면 남은 한 사람 3번은 나머지 물건을 가지며 될 것이다.

문제에서 "항상 물건들을 세 분류로 나눌 수 있도록 주어진다" 라고 하였다.

 

그렇다면 1번에게 배정할 수 있는 모든 경우의 수 

+ 1번에게 배정 후 남은 물건 중 2번에게 배정할 수 있는 경우의 수를 구한다.

▶ 순열과 조합 

순열과 조합 (백준 N과 M 시리즈)

 

이때, 배정하는 물건들의 합이 처음 배낭에 있었던 물건들의 평균 값어치를 넘어서면

동등하게 분배되지 않는 것이므로 조건이 들어간다.

▶ [BOJ] 15650 N과 M (2) (중복을 허용하지 않는 조합)

[BOJ] 백준 15650 N과 M (2)

---

#include <stdio.h>

const int CHILD = 3;
const int MAX_N = 2e3 + 2;
int selected[MAX_N], item[MAX_N];
int N, sum, avg, TC;
bool flag;

void init()
{
    for (int i = 0; i < MAX_N; i++)
    {
        selected[i] = item[i] = 0;
    }
    sum = flag = 0;
}

void input()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &item[i]);
        sum += item[i]; // 가진 아이템들의 총 값어치
    }
    // 3명의 아이들은 개수 상관없이
    // 동일한 값어치로 물건이 분배되어야 한다.
    avg = sum / 3; // 가진 아이템들의 평균 값어치
}

void DFS(int idx, int depth, int total)
{
    // 3번째에게 분배해야 하는 시점인 경우
    // 즉 1, 2번에게 분배가 끝난 경우
    if (depth == CHILD)
    {
        flag = true;
        return;
    }
    // 특정 인원에 대한 분류가 끝난 경우
    if (total == avg)
    {
        DFS(0, depth + 1, 0);
    }
        
    for (int i = idx; i < N; i++) {
        // 아직 선택되지 않은 물건 중
        if (selected[i] > 0) continue;
        
        // 아이가 지금까지 받은 물건 값어치가 평균보다 작은 경우
        if ((item[i] + total) <= avg)
        {    
            // 물건을 받은 아이를 표시
            selected[i] = depth;
            DFS(i, depth, (total + item[i]));
            
            // 1, 2번 분배가 끝나면 자동으로 3번째 아이에게 나머지를 할당하면 된다.
            if (flag) return;
            // 1, 2번이 분배가 완료될 때까지 DFS 할 수 있도록 원복
            selected[i] = 0;
        }
    }
}

void solve()
{
    // 물건 시작 인덱스
    // 물건 받을 아이
    // 해당 아이가 받은 물건의 총 값어치
    DFS(0, 1, 0);
    // 아직 선택되지 않은 아이템은 3번째 아이에게 배정
    for (int i = 0; i < N; i++)
    {
        if (!selected[i]) selected[i] = 3;
    }
}

void output(int tc)
{
    printf("#%d\n", tc);
    // 3명의 아이들에 대해 배정받은 물건 나열
    for (int child = 1; child <= 3; child++) {
        for (int j = 0; j < N; j++) {
            if (selected[j] == child) {
                printf("%d ", item[j]);
            }
        }
        printf("\n");
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; tc++)
    {
        init();
        input();
        solve();
        output(tc);
    }
    return 0;
}