14888-스타트와 링크

 

#include <iostream>
#include <vector>

using namespace std;
//Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
//번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

int N;
int visited[20];
int ability[20][20];
int MIN = 999999999;


void solve()
{
    int s=0;
    int l=0;
    
    for(int i=0;i<N;i++){
        if(visited[i]){
            for(int j=0;j<N;j++){
                if(visited[j])  s += ability[i][j];
            }
        }
        
        else if(!visited[i]){
            for(int j=0;j<N;j++){
                if(!visited[j]) l += ability[i][j];
            }
        }
    }

    int res = s > l ? s-l : l-s;
    if(res < MIN)   MIN =res;
    
}
        
void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        
    }
}

int main(void)
{
    cin >> N ;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            cin >>ability[i][j];
    }

    DFS(0,0);
    cout << MIN;
    
    return 0;
}

 

처음에 solve에서 스타트와 링크 벡터 각각 선언해줘서 

벡터에 insert하고 2중 for 문 각각 2개씩 돌려서 시간초과가 발생한 줄 알았다.

 

그래서 solve 함수를 visited 배열을 사용해서 2중 for문 하나로 바꿔줘서 제출했는데 또 시간초과

 

그래서 DFS 부분을 바꿔줬다. 

원래  idx가 없었는데 idx를 추가해줘서 visited가 1인지 확인하는 조건문 없애주고

for문을 idx부터 시작해서 돌리니까 드디어 맞았습니다.