https://school.programmers.co.kr/learn/courses/14760/lessons/125484
주어진 예시
- 각 종목별 학생들의 능력치 예시는 다음과 같다.
이 문제는 피로도 문제와 유사한 방식으로 구현 가능한 문제이다. 모두 학생 수 (또는 던전 개수)가 10개 이하로 적게 주어져 있다. 이 경우 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
실행 결과