[백준 3980번] 파이썬 - 선발 명단

백준 3980 - 선발 명단

시간 제한 1초, 메모리 제한 128MB

# 조건

• 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.!
• 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.
• 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다.
• 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.
• 이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오.
• 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 첫째 줄에는 테스트 케이스의 개수 C가 주어진다.
• 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 sij를 포함하고 있다.
• sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다.
• 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

출력

• 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다.
• 항상 하나 이상의 올바른 라인업을 만들 수 있다.

# 접근 방법

• 각 라인업에 선수를 채웠을 때 최댓값을 얻으면 되는 문제이다.
• 선수마다 배치될 수 있는 포지션이 최대 5개이므로 모든 경우를 확인하기 위하여 백트래킹을 이용해주었다.
• 함수의 인자로는 현재 몇 번째 선수인지, 현재 선수까지의 누적 능력치를 넣어주고
• 현재 선수가 11번째 선수라면 저장되어있는 result와 현재 누적 능력치를 비교해준다.
• 11번째 선수 이전이라면, 선수가 배정될 수 있는 포지션을 순회하며 idx+1, val + 능력치를 backtracking 함수의 인자로 재귀적 실행해준다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  

def backtracking(idx, val):  
    global result  
    if idx == 11:  
        if val > result:  
            result = val  
        return val  
    for i, j in enumerate(arr[idx]):  
        if not visited[i] and j:  
            visited[i] = True  
            backtracking(idx+1, val + j)  
            visited[i] = False  
    return  

T = int(input())  
for _ in range(T):  
    arr = [[*map(int, input().split())] for _ in range(11)]  
    visited = [False] * 11  
    result = 0  
    backtracking(0, 0)  
    print(result)