백준 14889. 스타트와 링크

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

14889번: 스타트와 링크

 

1. permutation을 돌리기 위해 인덱스로 사용할 벡터를 만든다

 n = 4라면 v = {1,1,0,0} : 1,2번이 같은팀
 n = 6라면 v = {1,1,1,0,0,0} : 1,2,3이 같은팀

 

2. 위 벡터를 이용해 두개의 벡터 startTeam, linkTeam에 각각의 팀원의 번호를 넣는다.

 

3. 루프를 돌면서 같은팀 팀원들간의 짝을 맞춰서 점수를 더한다. 

 

4. prev_permutation으로 v의 원소의 순서를 바꿔서 팀구성을 변경하고 2,3을 반복해서 점수차 중 최소인값을 찾는다.

 

 

 

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

int n;
int team[21][21];
int ans = 0;

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

    // indexing..
    // permutation을 돌리기위해서 인덱스로 사용할 벡터를 만든다
    // n = 4라면 v = {1,1,0,0}
    // n = 6라면 v = {1,1,1,0,0,0}
    vector<int> v;
    v.push_back(-1);
    for(int i = 1; i <= n/2; i++) {
        v.push_back(1);
    }
    for(int i = 1; i <= n/2; i++) {
        v.push_back(0);
    }

    // 최솟값 구하기 위해 루프 중 최초한번 ans값 설정위한 부울
    bool once = false;
    do {
        //for(int i = 1; i <= n; i++) cout << v[i] << ' ';
        //cout << endl;

        // 같은 팀인 인원들을 각자팀의 벡터에 넣는다
        // v = {1,1,0,0}이라면 첫두명이 한팀팀
        // v = {1,1,0,1,0,0} 이라면 1,2,4번째 인원이 한팀
        vector<int> startTeam; startTeam.push_back(-1);
        vector<int> linkTeam; linkTeam.push_back(-1);
        for(int i = 1; i <= n; i++) {
            if(v[i] == 1) {
                startTeam.push_back(i);
            }
            else {
                linkTeam.push_back(i);
            }
        }
        /*
        cout << "Teams... " << endl;
        for(int i = 1; i <= n/2; i++) cout << linkTeam[i] << ' ';
        cout << endl;
        for(int i = 1; i <= n/2; i++) cout << startTeam[i] << ' ';
        cout << "Size = " << startTeam.size() << '\n';
        */

        // sameTeam vector에는 같은 팀인 인원들이 있음
        int startTeamSum = 0;
        int linkTeamSum = 0;
        // (1,2) (1,3) (1,4) (2,3) (3,4) ... 이런식으로 두명씩 짝지음
        for(int i = 1; i <= startTeam.size()-1; i++) { // startTeam[0] = -1이므로 size-1만큼 루프
            for(int j = i+1; j <= startTeam.size()-1; j++) {
                startTeamSum += team[startTeam[i]][startTeam[j]];
                startTeamSum += team[startTeam[j]][startTeam[i]];

                linkTeamSum += team[linkTeam[i]][linkTeam[j]];
                linkTeamSum += team[linkTeam[j]][linkTeam[i]];
            }
        }
        /*
        cout << "startTeam = " << startTeamSum << '\n';
        cout << "linkTeam = " << linkTeamSum << '\n';
        cout << "sub is : " << startTeamSum - linkTeamSum << "\n\n";
         */
        // 두 팀의 점수의 차이
        int sub = startTeamSum - linkTeamSum;
        // 점수 차가 음수라면 양수로 바꿔줌
        if(sub < 0) sub *= -1;
        if(!once) { // 루프중 최초 한번 ans값 설정 
            ans = sub;
            once = true;
        }
        ans = min(ans, sub);
    } while(prev_permutation(v.begin()+1, v.end())); // permutation으로 v의 순서 변경 


    cout << ans;
}

 

---

백트래킹