[백준] 3980 - 선발 명단

1. 문제

3980번: 선발 명단

2. 개요

경기에 뛸 11명의 선수들의 각 포지션 별 능력치가 주어진다.

이 선수들로 스쿼드를 구성할 때, 가장 높은 능력치의 합이 되는 경우를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

0번 선수부터 아직 뽑지 않았거나 능력치가 0이라 뽑을 수 없는 경우를 제외한 0 ~ 10번까지의 포지션의 점수를 더하고 해당 포지션을 방문처리한 뒤 다음 선수로 넘어가는 작업을 반복한다.

10번 선수까지 이를 완료했다면 능력치의 총합과 현재까지 구한 능력치 합의 최대값을 비교해 갱신해나간 뒤 답을 출력한다.

3-2. Python

import sys

T = int(sys.stdin.readline())

for t in range(T):
    players = []
    visited = [1 for _ in range(11)]
    answer = 0

    def bt(idx = 0, l = []):
        global answer
        if idx == 11 and len(l) == 11:
            answer = max(answer, sum(l))

        for i in range(11):
            if visited[i] and players[idx][i]:
                visited[i] -= 1
                bt(idx + 1, l + [players[idx][i]])
                visited[i] += 1

    for i in range(11):
        players.append(list(map(int, sys.stdin.readline().split())))
    
    bt()

    print(answer)

3-3. C#

using System.ComponentModel;

namespace boj_3980
{
    internal class Program
    {
        static List<int[]> players;
        static bool[] visited;
        static int answer;

        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());

            for (int t = 0; t < T; t++)
            {
                answer = 0;
                players = new List<int[]>();
                visited = new bool[11];

                for (int i = 0; i < 11; i++)
                    players.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));

                BT(0, 0);

                Console.WriteLine(answer);
            }
        }

        static void BT(int idx, int stat)
        {
            if (idx == 11)
            {
                answer = (int)MathF.Max(answer, stat);
                return;
            }

            for (int i = 0; i < 11; i++)
            {
                if (!visited[i] && players[idx][i] > 0)
                {
                    visited[i] = true;
                    BT(idx + 1, stat + players[idx][i]);
                    visited[i] = false;
                }
            }
        }
    }
}