[백준] 15661번 : 링크와 스타트

문제

 

---

풀이

 

myunji.tistory.com/204

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

각 팀의 인원이 같아야했던 14889번과 달리 이 문제는 인원 수가 달라도 된다.

재귀함수로 풀어도 되지만 사실 이 문제는 비트마스크로도 풀 수 있다. 그래서 이번엔 비트마스크로 풀었다.

 

4명의 인원이 있다고 하자. 비트는 0 또는 1을 표시할 수 있으니 0은 링크팀, 1은 스타트팀이라고 하자.

0001 이라면 0번째 사람은 스타트팀, 1, 2, 3번째 사람은 링크팀인 것이다.

1100 이라면 0, 1번째 사람은 링크팀, 2, 3번째 사람은 스타트팀인 것이고...

 

각 팀의 인원은 최소 1명이라고 했으니까 팀이 한쪽으로 완전히 쏠린 0000과 1111을 제외하고

0001부터 1110까지 1씩 증가하며 힘의 차이를 계산하면 된다.

---

소스코드

 

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

using namespace std;

int power[20][20], N;

int calcPower(vector<int> v){ //각 팀의 power 계산
    int result = 0;

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

int splitTeam(int num) {
    vector<int> start, link;

    for (int i = 0; i < N; i++) {
        if ((num & (1 << i)) == 0) //해당 비트 0이면 링크팀
            link.push_back(i);
        else //해당 비트 1이면 스타트팀
            start.push_back(i);
    }
    return abs(calcPower(link) - calcPower(start)); //차이
}

int main() {
    int min_pow = -1;

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cin >> power[i][j];
    }
    for (int i = 1; i < ((1 << N) - 1); i++) { //N=4라면 0001~1110
        if (min_pow == -1) //최솟값 갱신
            min_pow = splitTeam(i);
        min_pow = min(min_pow, splitTeam(i));
    }
    cout << min_pow;
}

전체 소스코드다.

 

    for (int i = 1; i < ((1 << N) - 1); i++) { //N=4라면 0001~1110
        if (min_pow == -1) //최솟값 갱신
            min_pow = splitTeam(i);
        min_pow = min(min_pow, splitTeam(i));
    }

인원이 한 팀으로 쏠리는 두 경우를 제외하고 반복문을 돈다.

이 방법은 1010과 0101처럼 다른듯 하지만 계산하면 중복인 경우를 거르지 못한다.

 

int splitTeam(int num) {
    vector<int> start, link;

    for (int i = 0; i < N; i++) {
        if ((num & (1 << i)) == 0) //해당 비트 0이면 링크팀
            link.push_back(i);
        else //해당 비트 1이면 스타트팀
            start.push_back(i);
    }
    return abs(calcPower(link) - calcPower(start)); //차이
}

링크팀과 스타트팀을 구분하는 splitTeam 함수다.

num=0101이라고 해보자. i=0, 1, 2, 3이다.

1<<0 = 0001이고 이걸 0101과 &하면 0001이 된다. 이 값이 0이 아니기 때문에 0번째 사람은 스타트팀이다.

1<<1 = 0010이고 이걸 0101과 &하면 0000이 된다. 이 값이 0이기 때문에 1번째 사람은 링크팀이다.

 

이런식으로 팀을 나눠 벡터로 넣은 뒤 calcPower로 각 팀의 능력치를 계산한 뒤, 그 차이를 리턴한다.

 

int calcPower(vector<int> v){ //각 팀의 power 계산
    int result = 0;

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

각 팀의 능력치는 이렇게 구한다.