[PCCP 모의고사 #1_02] 체육대회

문제

https://school.programmers.co.kr/learn/courses/14760/lessons/125484

• 체육대회의 종목별 반 대표를 뽑으려고 할 때, 종목별 학생들의 능력치 합이 최대가 되는 경우의 능력치를 구하여라.

주어진 예시

• 각 종목별 학생들의 능력치 예시는 다음과 같다.
  

풀이

이 문제는 피로도 문제와 유사한 방식으로 구현 가능한 문제이다. 모두 학생 수 (또는 던전 개수)가 10개 이하로 적게 주어져 있다. 이 경우 DFS와 순열을 활용해 알고리즘을 구현할 수 있다.

• 실제로 주어진 값이 최대 15개 이하인 경우에는 DFS와 순열 방식으로 알고리즘을 구현할 수 있다.

코드

내 코드 (정답)

순열을 활용한 문제 풀이 방식이다.

from itertools import permutations
def solution(ability):
    answer = 0
    
    p = list(permutations(ability, len(ability[0])))
    
    for i in range(len(p)):
        total = 0
        for j in range(len(p[i])):
            total += p[i][j][j]
        answer = max(answer, total)
    
    return answer

실행 결과

강의 코드 (정답)

answer = 0
def DFS(L, s, ability, check):
    global answer
    n = len(ability)        # 학생 수
    m = len(ability[0])     # 종목 개수
    
    if L == m:
        answer = max(answer, s)   # 능력치 합의 최댓값을 구함
    else:
        for i in range(n):
            if check[i] == 0:
                check[i] = 1
                DFS(L+1, s + ability[i][L], ability, check)
                check[i] = 0


def solution(ability):
    global answer
    check = [0]*len(ability)
    DFS(0, 0, ability, check)      
    # Level, sum, ability, check
    # L : level (고를 수 있는 학생 수 중 몇 명째 선택한 것인지), sum : 능력치의 합
    
    return answer

실행 결과