문제설명:
당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다. 학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.
다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.
테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다. 하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.
당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.
이 문제에 아이디어는 permutations 를 사용한것이다.
permutations 이란 순열인데 123 중 2개 선택할때
12,13,23 이 아니라 12,13,23,21,32,31 이렇게 선택할 수 있는것이다. 중복순열은 따로 있다(product)
위에 그림예시로 할때 사람은 5명이고, 대표선수는 3명이 필요하다 즉 (1,2,3,4,5) 중에 3개를 선택하는것이다 학생수는 (1,2,3,4,5)이 되고 선택해야하는 종목이 3이 된다.
from itertools import permutations
def solution(ability):
res = 0
x, y = len(ability), len(ability[0])
lst = list(permutations([i for i in range(x)], y))[i for i in range(x)] 를 해주면 1~5 까지 리스트에 담아서, y갯수만큼 뽑아준다.
for i in lst:
ress = 0
idx = 0
for j in i:
ress += ability[j][idx]
idx += 1
if ress > res:
res = ress
return res초기값, idx 0 으로 해주고, ress에 하나씩 더해서 최대 합을 비교 해주면된다.
댓글