[백준] 14889번 스타트와 링크 C++

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

C++

#include<iostream>
#include<algorithm>
using namespace std;

int first[21][21];

/*
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
 */
int main() {
    int n,result = 1000000,diff;
    cin >> n;
    int team[n];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> first[i][j];
        }
    }
    // n = 4인 경우는 , 0,1,2,3 중에서 2개씩 선택한다.
    // 4C2를 해서 6가지 모두 구한다음에 가장 값 최소인거 하면 되지 않나?
    // 근데 (1,2) (3,4), (1,3) (2,4), (1,4) (2,3) / (2,3) (1,4), (2,4) (1,3), (3,4) (1,2)
    // 이렇게 되면 겹치는 경우 발생. 그럼 하프?
    // 일단 팀을 두 개로 쪼깨서 파악해본다.

    for(int j = 0; j < n; j++) { // 앞에 두 개는 0, 뒤에 두 개는 1로 넣어놓고 이걸로 조합 만들어서 비교해본다.
        if(j < n/2) {
            team[j] = 0; // 0, 1
        }
        else {
            team[j] = 1; // 2, 3
        }
    }
    do {
        int sumS = 0, linkS = 0;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(team[i] == 0 && team[j] == 0) {
                    sumS += first[i][j];
                }
                else if(team[i] == 1 && team[j] == 1) {
                    linkS += first[i][j];
                }
            }
        }
        
        diff = abs(sumS - linkS);
        if(result > diff) {
            result = diff;
        }

    }while(next_permutation(team, team+n));

    cout << result << "\n";
}

문제풀이

• 먼저, 스타트팀과 링크팀 두개로 나뉜다는 것에 집중했다. 그리고 n = 4일 때 0이 2개팀 1이 2개팀으로 나눈다고 가정하고 next_permutation 함수를 돌렸다. 그렇게 되면 (0,0,1,1), (0,1,0,1) 등 다양한 경우의 수를 모두 파악할 수 있다. 그리고 do-while문을 통해서 스타트팀과 링크팀의 차의 절댓값을 구하고 이 값들 중 최솟값을 출력하면 된다.

Comment

• 팀을 두 개로 나누는 것은 알고 있었지만, 이걸 어떻게 활용할지에 대해 오래 고민했던 것 같다. 최대한 STL을 사용하려고 하면서 0과 1이런식으로 나눈다는 것을 생각하게 됐고 next_permutation(team, team+n)을 사용하면서 모든 경우의 수를 파악할 수 있었다.