[재귀] BOJ 14889 스타트와 링크 - 오답노트

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

14889번: 스타트와 링크

- 문제 파악

NxN 배열에 임의 숫자들이 들어가 있고, 0부터 N-1 중에서 N/2 개의 숫자를 임의로 택한 숫자들의 원소의 합과 나머지 숫자들의 원소의 합의 차가 제일 작은 수를 출력한다. 

 

- 나의 접근

재귀로 접근하는 것은 좋았으나, 좀 더 경우의 수를 줄이려는 법을 찾다가 코드가 더 복잡해져버렸다. 직관적으로 접근해도 괜찮았을것 같다.

(지금까지 경험으로 직관적으로 했을때 시간초과가 날지 안날지 판단하는게 제일 어렵다)

 

- 정답

1. 스타트팀에 들어갈 팀원들을 재귀함수로 먼저 선택한다.
2. 1번에서 선택된 팀원들은 스타트팀 배열에, 선택되지 않은 팀원들은 모두 링크팀 배열에 넣는다.
3. 처음에 입력받은 NxN 배열을 모조리 돌면서 스타트팀의 점수와, 링크팀의 점수를 얻는다
4. 스타트팀 점수와 링크팀 점수의 차의 절대값을 계속 비교한다.
5. 모든 경우의 수를 1~4의 과정을 거친다.

#include "bits/stdc++.h"

using namespace std;

int check[22];
int arr[22][22];
int n;
int ans = 0x7fffffff;

int Team_Start[22];
int Team_Link[22];


void SetTeam(int nteamCnt, int idx)
{
    if (nteamCnt == n / 2)
    {
        int start = 0;
        int link = 0;

        int linkpos = 0;
        int startpos = 0;

        for (int i = 0; i < n ; i++)
        {
            if (!check[i])
            {
                Team_Link[linkpos++] = i;
            }
            else
            {
                Team_Start[startpos++] = i;
            }
        }


        for (int i = 0; i < n / 2; i++)
        {
            for (int j = 0; j < n / 2; j++)
            {
                start += arr[Team_Start[i]][Team_Start[j]];
                link += arr[Team_Link[i]][Team_Link[j]];
            }
        }

        ans = min(ans, abs(start - link));
        return;

    }

    for (int i = idx; i < n; i++)
    {
        if (!check[i])
        {
            check[i] = 1;
            SetTeam(nteamCnt + 1 , i);
            check[i] = 0;
        }

    }



}



int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;

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

    SetTeam(0,0);

    cout << ans;


}