[BOJ/백준][Gold5] 15661 : 링크와 스타트 (C++)

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

15661번: 링크와 스타트

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
N 제한이 20밖에 되지 않기 때문에 모든 경우의 수를 해보는 브루트포스 알고리즘으로 해결이 가능합니다.
재귀와 비트마스크를 이용한 방법이 가능한데, 비트마스크를 이용하였습니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N,d[20][20],ans=9e8;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%d",&d[i][j]);
    for(int i=0;i<(1<<N);i++){
        vector<int> a(N);
        vector<int> p,q;
        for(int j=0;j<N;j++){
            if(i&(1<<j)) {
                p.push_back(j);
                a[j]=1;
            }
            else q.push_back(j);
        }
        if(p.empty() || q.empty()) continue;
        int t1=0,t2=0;
        for(int j=0;j<p.size();j++){
            for(int k=0;k<p.size();k++){
                t1+=d[p[j]][p[k]];
            }
        }
        for(int j=0;j<q.size();j++){
            for(int k=0;k<q.size();k++){
                t2+=d[q[j]][q[k]];
            }
        }   
        ans=min(ans,abs(t1-t2));
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/15661.cpp