[BOJ 15661] 링크와 스타트

15661번: 링크와 스타트

 

삼성 알고리즘 특강 사전 문제를 풀면서 비트마스킹에 어려움을 느껴 비트마스킹 관련 문제를 풀어보았다.

 

1. 문제 설명

 

2. 구현 아이디어 1 - 시간 초과

비트마스킹을 활용하여 k번 사람이 어느 팀에 속했는지 표현하였다.

N=4일 때, 0은 링크 팀에 속해있고 1은 스타트팀에 속해있다는 의미이다.

 

0000: 모든 팀원이 링크 팀

0001: 1,2,3번 사람은 링크 팀, 4번은 스타트 팀

0011: 1,2번은 링크 팀, 3,4번은 스타트 팀

.

.

.

 

이렇게 비트마스킹을 활용하면 상태공간트리나 n차원 배열을 사용하지 않고 int형 정수로 팀 상황을 표현할 수 있다. 

 

그리고 0001일 때 링크 팀의 능력치 합은 {1,2}, {1, 3}, {2, 3} 쌍의 능력치의 합이다. 해당 팀에서 나올 수 있는 조합을 구한 뒤, 조합마다 능력치 합을 더하여 최종적으로 팀의 능력치를 구하였다.

조합은 아래 블로그를 참고하여 next_permutation를 사용해서 구현하였다.

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

 

마지막으로 두 팀의 능력치 차를 구하고, ret보다 작으면 갱신해주었다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 98765421

int n; // 전체 사람 수
int power[23][23]; // 능력치
int sp, lp;
int ret = INF;

int combi(vector<int> &v) {
    int p = 0;
    vector<bool> temp(v.size(), true);
    for (int i = 0; i < v.size()-2; ++i) {
        temp[i] = false;
    }

    do {
        vector<int> pair;
        for (int i = 0; i < v.size(); ++i) {
            if (temp[i]) pair.push_back(v[i]);
        }
        // pair이 비어있을 경우 index에 접근할 때 에러가 나기 때문
        if (pair.empty()) continue;
        p += power[pair[0]][pair[1]] + power[pair[1]][pair[0]];
    } while (next_permutation(temp.begin(), temp.end()));

    return p;
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    vector<int> ps(1 << n);

    for (int i = 0; i < (1<<n); ++i) { // 0000 ... 1111
        // 초기화
        vector<int> start;
        vector<int> link;
        sp = 0;
        lp = 0;

        // 비트마스킹으로 경우의 수 계산
        for (int j = 0; j < n; ++j) {
            if (i & (1<<j)) start.push_back(j);
            else link.push_back(j);
        }

        // 스타트 팀 조합 > 능력치 합 구해
        if (start.size() > 1) sp = combi(start);

        // 링크 팀 조합 > 능력치 합 구해
        if (link.size() > 1) lp = combi(link);

        // 둘이 abs 차와 ret을 비교해서 갱신
        if (abs(sp-lp) < ret) ret = abs(sp-lp);
    }

    cout << ret << "\n";

    return 0;
}

 

 

모든 조합의 수를 구하는 과정에서 시간 초과가 발생한 것 같다.

 

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

스타트와 링크 팀의 멤버를 비트마스킹으로 구한 것은 잘한 것 같은데 능력치 합을 어떻게 구할지 고민이였다.

결국 혼자 해답을 찾지 못하고 다른 분들의 블로그를 참고했다 🥲

 

해결 방법은 매우 간단했다 !! 굳이 팀원 쌍을 구하지 않고 멤버 번호가 저장된 배열에 2중 for문을 돌려서 능력치 합을 구할 수 있다 !!

int calcPower(vector<int> &v) {
    int p = 0;

    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < v.size(); ++j) {
            p += power[v[i]][v[j]];
        }
    }

    return p;
}

 

sp와 lp를 combi 함수 대신 calcPower 함수로 구해주도록 main 함수도 수정하여 문제를 해결할 수 있었다 :)

sp = calcPower(start);
lp = calcPower(link);
if (abs(sp - lp) < ret) ret = abs(sp - lp);