[백준/Baekjoon] 14889 스타트와 링크 C++ :: Back Tracking & Brute Force

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

14889번: 스타트와 링크

---

1. Logic

전체 인원의 반을 나눠서 팀을 구성하기 때문에 기저조건을 N/2로 설정한 후 DFS를 진행한다. N/2까지 갔을 때 전체인원의 반은 check배열에 true로 표시되어있고 반은 false로 표시되어 있을 것이다. true로 선택된 번호는 스타트 팀에 배정을 하고 false인 인원은 링크 팀에 배정을 하여 DFS를 돌며 최소값을 구한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input(21, vector<int> (21, 0));
bool check[21];

int n;
int ans = 0x3f3f3f3f;

void solve(int cnt, int prev) {
    if(cnt == n / 2) {
        int start = 0;
        int link = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(check[i]==true && check[j]==true) start+=input[i][j];
                if(check[i]==false && check[j]==false) link+=input[i][j];
            }
        }
        
        ans = min(ans, abs(start - link));
    }
    for(int i = prev+1; i < n; i++) {
        check[i] = true;
        solve(cnt+1, i);
        check[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> input[i][j];
        }
    }
    
    solve(0, 0);
    
    cout << ans;
    return 0;
}

 

 

---

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐