[프로그래머스] PCCP 모의고사 1회_2 체육대회 [Python]

• 문제 : https://school.programmers.co.kr/learn/courses/15008/lessons/121684
• dfs, 재귀
• 각 종목 별로 대표를 뽑고 능력치 합을 계산해 최댓값을 찾는다.

answer = 0

def dfs(d, sum, ability, ck):
    global answer
    
    n = len(ability)    # 학생 수
    m = len(ability[0]) # 종목 수
    
    if d == m:  # 깊이가 최대 종목 수에 도달하면
        answer = max(answer, sum)   # 더 큰 능력치 합으로 업데이트
        return
    else:   # 아니면
        for i in range(n):  # 학생 수 만큼 반복
            if ck[i] == 0:  # 종목 대표로 안 나간 학생이면
                
                ck[i] = 1   # 대표로 내보내고
                
                dfs(d+1, sum + ability[i][d], ability, ck)  # 다음 종목으로 이동, 능력치 합에 추가

                ck[i] = 0   # 대표에서 빼냄

def solution(ability):
    global answer
    
    ck = [0] * len(ability) # 대표로 나간 학생 체크 리스트
    
    dfs(0, 0, ability, ck)  # 깊이(현재 종목), 능력치 합, 2차원 리스트, 종목 체크 리스트
    
    return answer