[PCCP 모의고사#1] 체육대회 (itertools.permutation)

문제 설명

당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다. 학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.

다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.

	테니스	탁구	수영
석환	40	10	10
영재	20	5	0
인용	30	30	30
정현	70	0	70
준모	100	100	100

테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다.
하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.

당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.

제한 사항

• 1 ≤ ability의 행의 길이 = 학생 수 ≤ 10
• 1 ≤ ability의 열의 길이 = 종목 수 ≤ ability의 행의 길이
• 0 ≤ ability[i][j] ≤ 10,000
  • ability[i][j]는 i+1번 학생의 j+1번 종목에 대한 능력치를 의미합니다.

입출력 예

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

• 문제 예시와 같습니다.

입출력 예 #2

• 1번 학생이 2번 종목을, 2번 학생이 1번 종목의 대표로 참가하는 경우에 대표들의 해당 종목에 대한 능력치의 합이 최대가 되며, 이는 60입니다.

풀이

• 무지성 코딩의 유혹을 이기지 못하고 그냥 본능이 이끄는대로 풀어버렸다.
• 학생수와 종목수로 조합을 만들고, 조합으로 만든걸로 어빌리티 합산해서 더 크면 교체.
• 그렇게 루프가 끝나면 능력치 합의 최대값이 answer에 남게 된다.

import itertools

def solution(ability):
    answer = 0
    학생수 = len(ability)
    종목수 = len(ability[0])
    조합 = itertools.permutations([i for i in range(학생수)], 종목수)
    
    for i in 조합:
        _tmp = 0
        index = 0
        for j in i:
            _tmp += ability[j][index]
            index += 1
        if _tmp > answer:
            answer = _tmp
            
    return answer

정확성  테스트
테스트 1 〉	통과 (85.10ms, 10.3MB)
테스트 2 〉	통과 (26.23ms, 10.3MB)
테스트 3 〉	통과 (3388.17ms, 10.4MB)
테스트 4 〉	통과 (29.24ms, 10.4MB)
테스트 5 〉	통과 (0.71ms, 10.4MB)
테스트 6 〉	통과 (0.01ms, 10.5MB)
테스트 7 〉	통과 (0.35ms, 10.5MB)
테스트 8 〉	통과 (3520.79ms, 10.5MB)
테스트 9 〉	통과 (31.01ms, 10.4MB)
테스트 10 〉	통과 (57.89ms, 10.5MB)