[백준/Baekjoon] 15661 링크와 스타트 C++ :: Brute Force

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

15661번: 링크와 스타트

---

1. Logic

팀을 꾸릴때 인원이 최대 20명이고 1명부터 팀을 꾸릴 수 있기 때문에 시간복잡도가 19!이 나온다. 이렇게 되면 시간복잡도를 한참 뛰어넘기 때문에 로직을 생각해 봐야 한다.

우리는 두 팀의 능력치의 절댓값을 판단해야 하기 때문에 1, 2, 3, 4의 인원으로 팀을 꾸리면 1,2 를 골라서 팀을 꾸리는 것과 3, 4를 골라서 팀을 꾸려서 능력치를 비교하면 결과값을 똑같이 나오기 때문에 최대 n/2까지 돌아서 계산하면 10!=3628800이 나오기 때문에 2초안에 충분히 돌 수 있다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;
int ans = 0x3f3f3f3f;

int input[21][21];
bool check[21];

int rateCalc() {
    int startRate = 0;
    int linkRate = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(check[i] && check[j]) {
                startRate += input[i][j];
            }
            else if(!check[i] && !check[j]) {
                linkRate += input[i][j];
            }
        }
    }
    
    return abs(startRate-linkRate);
}

void solve(int cnt, int idx) {
    if(cnt > n/2) return;
    
    if(cnt > 0) {
        ans = min(ans, rateCalc());
    }
    
    for(int i = idx; i < n; i++) {
        check[i] = true;
        solve(cnt+1, i+1);
        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;
}

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