백준 14889 스타트와 링크 c++

 

 

 

처음 구상한 알고리즘은 다음과 같다.

하지만 부분 집합을 구해 (n명을 두 팀으로 나눠 불러오는 과정, 이때 모든 경우의 수를 고려해 불러와야함) 불러오는 부분을 어떻게 구현할 지 생각해야했다.

#include <iostream>
using namespace std;

int main(){
    
    //입력받기
    int n;
    cin >> n;
    
    int arr[n][n];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> arr[i][j];
    
    // 팀이 될 수 있는 경우의 수 계산 (n C n/2)
    int num = 1;
    for(int i=n; i>(n/2); i++)
        num *= i;
    for(int i=1; i<=(n/2); i++)
        num /= i;
    
    //팀이 될 수 있는 경우의 수만큼 돌며 모든 경우를 고려해줌
    int answer = 101; //두 팀의 능력치 차이 값을 저장, 가장 작은 경우(min)를 골라내기
    for(int i=0; i<(num); i++){ 
        //팀이 될 수 있는 경우하나씩 불러옴(팀 2개 형태)
        
        //각 팀의 능력치 합(s1, s2) 계산
        
        //둘의 차이(|s1과 s2의 차이|)가 answer보다 작으면 answer값 갱신
    }
    
    //답 출력
    cout << answer;
    
    return 0;
}

 

 

 

최종 해결한 방법은 다음과 같다.