Search

PGS 체육대회

태그
브루트포스 알고리즘

문제 설명

•
주어진 학생들의 능력치 배열에서 각 종목에 대해 대표를 뽑아 능력치 합을 최대화하는 값을 구하는 문제
테니스
탁구
수영
석환
40
10
10
영재
20
5
0
인용
30
30
30
정현
70
0
70
준모
100
100
100

예제 입력/출력

ability
result
[[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]
210
[[20, 30], [30, 20], [20, 30]]
60

제약 조건

•
1≤∣ability∣=1 ≤ |ability| = 학생 수 ≤10≤ 10
•
1≤∣ability[0]∣=1 ≤ |ability[0]| = 종목 수 ≤≤ 학생 수

문제 풀이

풀이 브루트 포스 - 상한 O(10!)O(10!)

풀이 코드

from itertools import permutations def solution(ability): n = len(ability) # 학생 수 m = len(ability[0]) # 종목 수 ans = 0 # 모든 가능한 경우의 수를 계산 (순열) for person_idxs in permutations(range(n), m): tmp = 0 for s_idx, p_idx in enumerate(person_idxs): tmp += ability[p_idx][s_idx] ans = max(ans, tmp) return ans
Python
복사