[C++ / 백준 14889번] (재귀 / 비트마스크) 스타트와 링크

 

 

 

 

재귀는 항상 어려운 것 같다. 이해도 이해지만 이 풀이 방식을 기억해 놓는 것도 좋을 것 같다.

 

다 풀어놓고 실수 한 점은 팀이 3,3 으로 나뉘었을 때 (0,1) (0,2) (1,2) 등등 모든 순서쌍을 고려 해야 하는데 그러지 않았다. 모든 순서쌍을 더할 수 있는 코드로 고치니 풀이에 성공했다.

 

vector find, 조합, 백트래킹, DFS 를 통해 풀이했다.

 

 

재귀 풀이

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


int N;
int mindiff = 99999999;
int arr[20][20];

int ans[10];
vector<int> v1, v2;

int cal(vector<int> v) {

    int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        for (int j = i + 1; j < v.size(); j++) {
            sum += arr[v[i]][v[j]] + arr[v[j]][v[i]];
        }
    }
    return sum;
}

void func(int depth,int next)
{
    if (depth >= N / 2)
    {

        v2.clear();

        for (int i = 0; i < N; i++) {
            if (find(v1.begin(), v1.end(), i) == v1.end()) {
                v2.push_back(i);
            }
        }
    
        mindiff = min(mindiff, abs(cal(v1) - cal(v2)));

        return;
    }

    for (int i = next; i < N; i++)
    {
       
        v1.push_back(i);
        func(depth + 1, i + 1);
        v1.pop_back();

    }
}

int main() 
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> arr[i][j];
        }
    }

    func(0, 0);

    cout << mindiff;

    return 0;
}

 

 

비트마스크 풀이

 

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

int N;
int arr[20][20];
int ans = 9999999999;
vector<int> t1;
vector<int> t2;


int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < (1 << N); i++)
    {
        
        t1.clear();
        t2.clear();

        for (int k = 0; k < N; k++)
        {

            if (i & (1 << k))
            {
                t1.push_back(k);
            }
            else
            {
                t2.push_back(k);
            }
           
        }

        
        if (t1.size() > N / 2 || t2.size() > N / 2) continue;

        int sum1 = 0;
        int sum0 = 0;
        for (int a = 0; a < N / 2; a++)
        {
            for (int b = 0; b < N / 2; b++)
            {
                sum1 += arr[t1[a]][t1[b]];
                sum0 += arr[t2[a]][t2[b]];

            }
        }

        ans = min(ans, abs(sum1 - sum0));




    }

    cout << ans;



    return 0;
}