15661번

15661번 - 링크와 스타트

'스타트와 링크' 문제랑 흡사하게 만든 다른 문제이다. 기존문제랑 다르게 이 문제는 팀을 절반으로 나누지않아도 된다. 그냥 1명이상 팀이 유

지되면 된다는 조건이 있기 때문에 약간 다르다.

나는 그냥 완전탐색을 통해, 1번팀으로 뽑는다/ 뽑지 않는다 이런방식으로 완전탐색을 진행하였다. 왜냐하면 N제한이 20이기 때문에 시간복

잡도가 O(2^20) 으로 충분히 실행이 가능하다고 생각했기 때문이다. 하지만 이런 방식은 중복되는 값들을 다시 한번 계산하게 되므로 좀 더 

시간 복잡도를 줄여서 풀 수 있을 것 같다. ( 빨리 푸신 분들은 DP로 접근한 듯 하다)

중복된다는 것은 i번 사람을 1번 팀으로 뽑고, 전부다 2번 팀으로 뽑는 경우와 i번 사람을 2번 팀으로 뽑고, 나머지를 1번 팀으로 다 뽑는 경우

가 겹치게 된다. 이 부분을 주의해서 시간복잡도를 줄이면 될 것 같다.

<정답 코드>

#include<iostream>
#define INF 987654321
using namespace std;
 
int N;
int map[20][20];
int ans = INF;
int team[20];
void dfs(int k, int cnt1,int cnt2)
{
    if (k == N)
    {
        // 팀원이 1명이상이 아니면 리턴
        if (cnt1 == 0 || cnt2 == 0)
            return;
 
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (team[i] == 1 && team[j] == 1)
                    sum1 += map[i][j];
                if (team[i] == 0 && team[j] == 0)
                    sum2 += map[i][j];
            }
        }
        if (ans > abs(sum1 - sum2))
            ans = abs(sum1 - sum2);
 
        return;
    }
 
 
    // 1번 팀으로 뽑는다.
    team[k] = 1;
    dfs(k + 1,cnt1+1,cnt2);
 
    // 1번 팀으로 뽑지 않는다.
    team[k] = 0;
    dfs(k+1,cnt1,cnt2+1);
 
 
}
int main()
{
 
    //freopen("input.txt", "r", stdin);
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    dfs(0, 0,0);
 
    cout << ans << endl;
    return 0;
}