[BOJ 14889] 스타트와 링크

14889번: 스타트와 링크

 

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다!!

조합을 활용하여 문제를 풀었다. 문제를 푼 자세한 로직은 아래와 같다.

1. 조합을 사용해서 N/2개의 수를 고른다. 해당 수를 start 팀에 배정한다.
2. 반복문으로 N/2개의 수를 고른 경우의 수마다 3번부터 6번 과정을 수행한다.
3. 0 ~ N-1 중 start 팀에 배정되지 않은 수는 link 팀에 배정한다.
4. 조합을 사용해서 0 ~ N/2 중 2개의 수(i, j)를 고른다. 해당 수는 인덱스를 의미하게 된다.
5. start, link에서 각각 인덱스에 해당하는 원소인 선수의 능력치 합을 팀의 능력치에 더한다. ex) sPower = powers[s[i]][s[j]] + powers[s[j]][s[i]]
6. start와 link 팀의 능력치 차이를 구하여 현재 팀의 능력치 차이보다 작다면 해당 값으로 갱신한다.

 

(C++) 조합(Combination) 구현하기

조합은 위 블로그를 참고하여 next_permutation으로 구현하였다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

#define INF 987654321

// 조합
vector<vector<int>> combination(int n, int k) {
    vector<bool> v(n-k, false);
    v.insert(v.end(), k, true);

    vector<vector<int>> ret;
    do {
        vector<int> temp;
        for (int i = 0; i < n; ++i) {
            if (v[i]) temp.push_back(i);
        }
        ret.push_back(temp);
    } while (next_permutation(v.begin(), v.end()));

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<vector<int>> powers = vector<vector<int>>(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> powers[i][j];
        }
    }

    int ret = INF;
    vector<vector<int>> group = combination(n, n/2);

    // N/2명으로 이루어진 스타트 팀을 조합으로 구한다
    for (auto start : group) {
        // N명 중 start에 속하지 않은 사람은 링크 팀으로 배정
        vector<int> link;
        for (int i = 0; i < n; ++i) {
            if (find(start.begin(), start.end(), i) == start.end()) link.push_back(i);
        }

        // 팀 내에서 2명씩 짝짓는 경우의 수를 구해 팀의 능력치 계산
        int sPower = 0;
        int lPower = 0;
        vector<vector<int>> pCombi = combination(n/2, 2);
        for (auto v : pCombi) {
            sPower += (powers[start[v[0]]][start[v[1]]] + powers[start[v[1]]][start[v[0]]]);
            lPower += (powers[link[v[0]]][link[v[1]]] + powers[link[v[1]]][link[v[0]]]);
        }

        // 팀 능력치 차이가 최소가 되도록 ret 갱신
        ret = min(ret, abs(sPower-lPower));
    }

    cout << ret << "\n";

    return 0;
}

 

이렇게 푼다면 최대 연산 횟수는 아래와 같다.

 

해당 값은 190 * 45 = 8,550으로 조합을 사용하여 풀어도 시간 제한(2초) 안에 넉넉하게 풀 수 있다.

 

3. 구현 아이디어 2 - 코드 개선

문제가 익숙하다고 생각했는데 이전에 풀었던 문제와 유사한 문제였다 ...!

[BOJ 15661] 링크와 스타트

 

해당 글을 다시 읽어보며 sPower와 lPower을 구하는 코드를 아래와 같이 수정하였다. (그때도 똑같이 실수한 부분 ㅠuㅠ)

조합을 사용하지 않고 이중 for문을 돌면 모든 쌍의 능력치를 합할 수 있다.

for (int i = 0; i < n/2; ++i) {
    for (int j = 0; j < n / 2; ++j) {
        sPower += powers[start[i]][start[j]];
        lPower += powers[link[i]][link[j]];
    }
}

 

 

소요 시간을 2000ms에서 156ms로 줄일 수 있었다.