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

문제

 

---

풀이

 

팀을 나누는게 가장 중요한 문제이다.

6명이 있을 때 3명을 고르고 나면 선택받은 3명은 스타트팀 선택받지 못한 3명은 링크팀에 넣어 계산하면 될 것이다.

근데, (1,2,3)번 사람을 고르는 것과 (2,1,3)번 사람을 고르는 것은 같은 경우이다.

이런 경우를 어떻게 제외할 수 있을까?

 

myunji.tistory.com/198?category=1154147

[백준] 15650번 : N과 M (2)

위 문제는 숫자를 오름차순으로 뽑는 모든 경우를 구하는 문제였다.

이 문제도 선수를 오름차순으로 뽑는다면 중복을 없앨 수 있을 것이다.

---

소스코드

 

#include <iostream>
#include <cmath>

using namespace std;

bool isTeam[20] = {0,};
int pow_matrix[20][20];
int N, min_pow = 1000;

int cal_min() {
    int start_pow = 0, link_pow = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (isTeam[i] && isTeam[j]) //체크 된거면 스타트팀
                start_pow += pow_matrix[i][j];
            if (!isTeam[i] && !isTeam[j]) //체크 안된건 링크팀
                link_pow += pow_matrix[i][j];
        }
    }
    return abs(start_pow - link_pow);
}

void split_team(int index, int player) {
    if (index == (N / 2)) { //절반 구하면 계산
        int result = cal_min();
        if (result < min_pow)
            min_pow = result;
    }
    for (int i = player; i < N; i++) { //오름차순으로 뽑아서 중복 제거
        if (!isTeam[i]) {
            isTeam[i] = true; //내려감
            split_team(index + 1, i + 1);
            isTeam[i] = false; //올라감
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> pow_matrix[i][j];
        }
    }
    split_team(0, 0);
    cout << min_pow;
}

전체 소스코드이다.

 

void split_team(int index, int player) {
    if (index == (N / 2)) { //절반 구하면 계산
        int result = cal_min();
        if (result < min_pow)
            min_pow = result;
    }
    for (int i = player; i < N; i++) { //오름차순으로 뽑아서 중복 제거
        if (!isTeam[i]) {
            isTeam[i] = true; //내려감
            split_team(index + 1, i + 1);
            isTeam[i] = false; //올라감
        }
    }
}

절반의 선수만 뽑으면 되니까 함수의 종료조건은 index == (N / 2)이다.

선수를 뽑으면 cal_min() 함수를 호출해 각 팀의 능력치의 차이를 구하고 기존의 값과 비교해 갱신한다.

 

선수를 뽑는 과정의 코드는 위에 링크로 올려놓은 15650번과 매우 유사하다.

isTeam에 true로 체크된 사람들이 스타트팀으로 들어갈 것이다.

 

int cal_min() {
    int start_pow = 0, link_pow = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (isTeam[i] && isTeam[j]) //체크 된거면 스타트팀
                start_pow += pow_matrix[i][j];
            if (!isTeam[i] && !isTeam[j]) //체크 안된건 링크팀
                link_pow += pow_matrix[i][j];
        }
    }
    return abs(start_pow - link_pow);
}

선수들의 능력치를 구하는 cal_min 함수이다. 복잡하지 않으니 굳이 설명할 필요는 없을 것 같다.