[백준 3980] 선발 명단

문제

11명의 선수들에 대한 각 포지션별 능력치가 주어졌을 때 선수 들을 어디에 배치해야 가장 높은 전력을 취할 수 있는지 구하라. 능력치가 0이라는 것은 해당 포지션에 배치할 수 없다는 뜻이다.

 

입력

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

 

출력

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

---

접근

각 행에 접근하면서 해당 열을 이전에 방문하지 않았을 때 능력치를 더하여 다음으로 넘어간다.

처음에 0을 처리하지 못했었다. 따라서 0이거나 이전에 방문한 적이 있을 때는 continue 그렇지 않다면 해당 능력치를 total에 더하여 다음으로 넘어가도록 한다.

 

구현

- y는 행에 대한 인덱스를 의미한다. 이를 하나씩 증가시키면서 선수를 적합한 포지션에 배치한다.

- total은 지금까지 선택한 선수들의 능력치 합이다.

- for문을 통해 해당 선수의 포지션 별 능력치를 탐색한다.

- 이전에 해당 포지션에 선수를 배치했거나 능력치가 0이면 continue

- 그렇지않다면 해당 선수를 그 포지션에 배치시키고 재귀호출을 진행한다.

- 11명을 모두 선택했을 때 최댓값 비교를 한다.

def solve(y, total):
    global answer, visited
    if y == 11:
        answer = max(answer, total)
        return

    for x in range(11):
        if visited[x]:
            continue
        if squad[y][x] == 0:
            continue
        total += squad[y][x]
        visited[x] = True
        solve(y+1, total)
        total -= squad[y][x]
        visited[x] = False

---

전체 코드

import sys
input = sys.stdin.readline

def solve(y, total):
    global answer, visited
    if y == 11:
        answer = max(answer, total)
        return

    for x in range(11):
        if visited[x]:
            continue
        if squad[y][x] == 0:
            continue
        total += squad[y][x]
        visited[x] = True
        solve(y+1, total)
        total -= squad[y][x]
        visited[x] = False


test_case = int(input())
for _ in range(test_case):
    squad = [list(map(int, input().split())) for _ in range(11)]
    visited = [False] * 11
    answer = 0

    solve(0, 0)
    print(answer)