[백준/BOJ] 14889번 스타트와 링크 (C++)

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

삼성 역량 테스트 기출 문제 : DFS(조합) or 순열

next_permutation을 이용하여 팀을 나눠줍니다. (예를들어 0, 0, 1, 1 로 시작) 0은 start팀, 1은 link팀으로 나누어 각각의 합을 구하고 두 합의 차이의 최소값을 찾으면 간단히 해결할 수 있습니다. DFS를 이용하는 경우 조합을 구하여 true는 start팀, false는 link팀으로 나누어 동일하게 해결할 수 있습니다.

 

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

int map[21][21];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 2147000000;
    cin>>n;
    for(int i = 1; i <= n; i++) {
    	for(int j = 1; j <= n; j++) {
    		cin>>map[i][j];
		}
	}
	
	vector<int> tmp(n, 1);
	for(int i = 0; i < n / 2; i++) {
		tmp[i] = 0; // 0, 0, 1, 1
	}
	
	do {
		vector<int> start, link;
		for(int i = 0; i < n; i++) {
			if(tmp[i] == 0) start.push_back(i + 1);
			else link.push_back(i + 1);			
		}
		
		int sumS = 0, sumL = 0;
		for(int i = 0; i < n / 2; i++) {
			for(int j = 0; j < n / 2; j++) {
				if(i == j) continue;
				sumS += map[start[i]][start[j]];
				sumL += map[link[i]][link[j]];
			}
		}
		answer = min(answer, abs(sumS - sumL));
	} while(next_permutation(tmp.begin(), tmp.end()));
	
	cout<<answer;
}

 

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

int n, answer = 2147000000;
int map[21][21];
bool check[21];

int getSub() {
    vector<int> start, link;
    for(int i = 1; i <= n; i++) {
        if(check[i]) start.push_back(i);
        else link.push_back(i);
    }
    
    int sumS = 0, sumL = 0;
    for(int i = 0; i < n / 2; i++) {
        for(int j = 0; j < n / 2; j++) {
            if(i == j) continue;
            sumS += map[start[i]][start[j]];
            sumL += map[link[i]][link[j]];
        }
    }
    
    return abs(sumS - sumL);
}

void DFS(int idx, int cnt) {
    if(cnt == n / 2) {
        answer = min(answer, getSub());
        return;
    } else {
        for(int i = idx; i <= n; i++) {
            check[i] = true;
            DFS(i + 1, cnt + 1);
            check[i] = false;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin>>map[i][j];
        }
    }
    
    DFS(1, 0);
    cout<<answer;
}