[ 백준 3980 ] 선발 명단 (C++)

백준의 선발명단(3980) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 11명의 선수들이 갈 수 있는 라인에 섰을 때, 팀의 능력치가 최대치가 되는 경우를 찾아야 하는 문제이다.

   모든 경우를 다해봐야 하는 브루트포스 문제이다.

   먼저 전체적인 문제 풀이 과정에 대해서 설명하자면, 본인은 0번부터 10번까지의 선수들이 0번라인부터 10번라인까지

   고르는 경우로 생각을 했고, 0번 사람을 기준으로 구현하였다.

   0번 사람이 갈 수 있는 라인이라면 0번 선수를 그 라인으로 보내놓고, 나머지 10명의 선수들이 남은 라인을 찾아가면서

   팀의 에너지값이 최대치가 될 때마다 갱신해 주는 식으로 구현하였다.

  

   [ 조합 구현 하는 방법 알아보기 ]

   [ 순열 구현 하는 방법 알아보기 ]

   본인은 이 문제를 해결하기 위해서 Player[][] 이라는 2차원 int형 배열과, Select[] bool형 1차원 배열을 사용하였다.

   Player[a][b]의 의미는 a번 선수가 b번 포지션에 갔을 때의 능력치를 의미하고

   Select[a] = true 의 의미는 a번 포지션은 이미 다른 선수가 자리를 차지하고 있습니다 를 의미한다.

2) 재귀를 통해서 11명의 선수들을 11개의 포지션에 넣어주었다. (본문함수 : Choice(int, int))

   매개변수로는 포지션을 선택할 사람의 번호와, 선택한 사람들로만의 팀의 능력치를 받아왔다.

   1)의 설명대로 본인은 0번 선수를 뽑아주고, 나머지 선수들을 뽑았다.

for (int i = 0; i < 11; i++)
    {
        if (Player[0][i] != 0)
        {
            Select[i] = true;
            Choice(1, Player[0][i]);
            Select[i] = false;
        }
    }

   이런식으로 ! 0번 선수가 i번 포지션에 갈 수 있다면, i번 포지션은 선택되었다고 표시해주고, Choice함수를 호출하였다.

   Choice(1, Player[0][i]) 의 의미는 이제 다음번에 뽑을 선수는 1번 선수이고, 현재까지 팀의 능력치는

   0번선수가 i번 포지션에 갔을 때의 능력치 입니다. 가 된다.

  

3) 위와 같은 방식으로 모든 선수들에 대해서 구현을 해주면 된다. 최댓값은 첫번째 매개변수 값이 11이 되면

   즉, 11명이 모두 라인을 선택했으면 팀의 능력치를 계산 비교하면서 갱신해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
using namespace std;
 
int Player[11][11], Answer;
bool Select[11];
 
void Initialize()
{
    Answer = 0;
    memset(Select, false, sizeof(Select));
    memset(Player, 0, sizeof(Player));
}
 
void Input()
{
    for (int i = 0; i < 11; i++)
    {
        for (int j = 0; j < 11; j++)
        {
            cin >> Player[i][j];
        }
    }
}
 
void Choice(int Np, int Sum)
{
    if (Np == 11)
    {
        if (Answer < Sum) Answer = Sum;
        return;
    }
 
    for (int i = 0; i < 11; i++)
    {
        if (Player[Np][i] != 0 && Select[i] == false)
        {
            Select[i] = true;
            Choice(Np + 1, Sum + Player[Np][i]);
            Select[i] = false;
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < 11; i++)
    {
        if (Player[0][i] != 0)
        {
            Select[i] = true;
            Choice(1, Player[0][i]);
            Select[i] = false;
        }
    }
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}