[백준 14889][C++] 스타트와 링크 (Silver 3)

[문제보기]

 14889. 스타트와 링크

14889번: 스타트와 링크

[풀이방법]

n의 최대가 20이므로 재귀를 사용했을 때 시간 안에 계산을 할 수 있다. O(n^2)

따라서 dfs()를 사용하여 모든 경우의 수에 대해서 스타트팀과 링크팀의 차이를 계산하여 최솟값을 찾았다.

1. dfs(int cnt)

    cnt는 dfs()가 몇 번 진행이 됐는지 확인하는 변수인데, 이 변수가 n+1이 되고 각 팀에 n/2 만큼 입력이 하면 

    get_min() 함수를 진행한다. 

    

    밑에 있는 코드는 start와 link에 사람을 넣는 모든 경우의 수를 만들어낸다.

 

2. get_min()

    s_power, l_power 변수를 만들어서 각 팀에 대한 힘을 더한 뒤 그 차이를 절댓값으로 return 해준다.

[소스코드]

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int n, ans = 987654321;
int s[21][21] = {0};
vector<int> start;
vector<int> link;


int get_min(){
    int s_power =0;
    int l_power =0;

    for(int i=0; i<n/2; i++){
        for(int j=0; j<n/2; j++){
            if(i==j)
                continue;

            s_power += s[start[i]][start[j]];
            l_power += s[link[i]][link[j]];
        }
    }
    
    return abs(s_power - l_power);
}

void dfs(int cnt){
    if(cnt == n+1){
        if(start.size() == n/2 && link.size() == n/2){
            ans = min(ans, get_min());
        }
        return;
    }

    start.push_back(cnt);
    dfs(cnt+1);
    start.pop_back();

    link.push_back(cnt);
    dfs(cnt+1);
    link.pop_back();

}

int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> s[i][j];
        }
    }

    dfs(1);

    cout << ans << "\n";
}

 

[해결과정 중 실수한 부분]

맨 처음에는 bool 자료형을 갖는 team이라는 변수를 만들어 dfs()를 만들어 n/2씩 나눠지는 경우의 수를 만들고, get_min() 함수에서 vector를 만들어 각각 s_power, l_power변수를 사용하여 계산을 하였다. 

하지만 get_min() 함수에 들어갈 때마다 vector함수를 만들고, 각각 이중 포문을 사용하여 계산을 하기 때문에

시간 초과가 나왔다. ㅠㅠ

int get_min(){
    vector<int> start;
    vector<int> link;
    int s_power =0;
    int l_power =0;

    for(int i=1; i<=n; i++){
        if(team[i]){
            start.push_back(i);
        }
        else{
            link.push_back(i);
        }
    }

    for(int i=0; i<start.size(); i++){
        for(int j=0; j<start.size(); j++){
            if(i == j)
                continue;
            s_power += s[start[i]][start[j]];
        }
    }

    for(int i=0; i<link.size(); i++){
        for(int j=0; j<link.size(); j++){
            if(i == j)
                continue;
            l_power += s[link[i]][link[j]];
        }
    }
    
    return abs(s_power - l_power);
}

void dfs(int cnt){
    if(cnt == n/2){
        ans = min(ans, get_min());
        return;
    }

    for(int i=1; i<=n; i++){
        if(!team[i]){
            team[i] = true;
            dfs(cnt+1);
            team[i] = false;
        }
    }

}