[백준3980] 선발 명단

www.acmicpc.net/problem/3980

3980번: 선발 명단

---

풀이

 

S의 ij는 i번 선수가 j번 포지션에서 뛸 떄의 능력이다

 

visited에 이미 방문한 포지션을 체크한다. 방문한 포지션, 자신이 뛸 수 없는 포지션을 제거하고 가능한 포지션들을 재귀적으로 호출한다.

 

즉, 백트래킹 기법을 사용해 모든 경우를 탐색한다.

 

함수의 매개변수는 (맵, 선택한 인원, 능력치합, 방문체크)로 구성한다.

 

---

시간복잡도

재귀가 최대로 깊어진다고 해보자

가능한 포지션이 최대 5개이고 11명이 있다.

그러므로 재귀는 최대 55번보단 작게 일어난다.

재귀 한번당 11개의 인수를 가진 for문이 한번씩 돈다.

 

선수가 n이라면

 

시간복잡도는 O(n^2)이다. n=11이니 충분히 모든경우 탐색 가능하다.

 

---

코드

import sys
input = sys.stdin.readline

def f(mat,n,sum,vistied):
    if n == 11:
        return sum
    answer = 0
    for i in range(11): #n번째 선수의 뛸 수 있는 포지션
        if mat[n][i] != 0 and not visited[i]:
            visited[i] = 1
            answer = max(f(mat,n+1,sum+mat[n][i],visited),answer)
            visited[i] = 0
    
    return answer

T = int(input())
for _ in range(T):
    mat = [list(map(int,input().split())) for i in range(11)]
    visited = [0]*11

    answer = f(mat,0,0,visited)

    print(answer)