3980번: 선발 명단
각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.
www.acmicpc.net
문제
챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.
오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.
수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.
이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 $s_{ij}$를 포함하고 있다. $s_{ij}$는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)
출력
각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.
코드
import sys
input = sys.stdin.readline
ans = 0
def place(visited, ability, idx, cnt, max_v):
global ans
if idx >= 11:
ans = max(ans, max_v)
return
for p in range(11):
if not visited[p] and ability[idx][p] > 0:
visited[p] = True
place(visited, ability, idx+1, cnt+1, max_v+ability[idx][p])
visited[p] = False
for _ in range(int(input())):
ability = []
for i in range(11):
ability.append(list(map(int, input().split())))
ans = 0
visited = [False] * 11
place(visited, ability, 0, 0, 0)
print(ans)
재귀함수를 이용하여 풀이하였다. visited 배열은 j번 포지션에 이미 선수를 배치하였는지 체크하기 위하여 사용됐다.
place 함수는 p가 아직 선수를 배치하지 않은 포지션이고 idx번 선수가 p에 배치가 가능할 때만 재귀적으로 호출된다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 번 직사각형 탈출 (0) | 2023.09.05 |
---|---|
[Python/파이썬] 백준 16988번 Baaaaaaaaaduk2 (Easy) (0) | 2023.08.31 |
[Python/파이썬] 백준 17471번 게리맨더링 (0) | 2023.08.26 |
[Python/파이썬] 백준 21937번 작업 (0) | 2023.08.19 |
[Python/파이썬] 백준 17090번 미로 탈출하기 (0) | 2023.08.17 |