프로그래머스 체육대회 (LV2)[PCCP 모의고사1]
문제
당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 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
3
4
5
6
7
8
9
10
11
12
13
14
from itertools import permutations
def solution(ability):
answer = 0
p = list(permutations(ability, len(ability[0])))
print(p)
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
설명
| 테니스 | 탁구 | 수영 | |
|---|---|---|---|
| 석환 | 40 | 10 | 10 |
| 영재 | 20 | 5 | 0 |
| 인용 | 30 | 30 | 30 |
| 정현 | 70 | 0 | 70 |
| 준모 | 100 | 100 | 100 |
이런식으로 테이블이있을떄, 테이블의 가로,세로 최대길이가 10이므로, 완전탐색으로 풀려고 접근하였다.
즉, 선수들이 서로 종목이 겹치지 않게 대회에 참가하는 모든 경우의 수를 구해서, 그중 가장 큰값을 구하면 되는 것이다.
필자는 처음에 종목별로 하나식 뽑아서 모든 경우의 수를 구하려 했으나, 주어지는 ability배열이 선수별로 종목에대한 능력치가 주어져있었다.
즉 가로로 한줄씩 주어져있던 것이다.
그럼 생각을 바꿔서,
| 테니스 | 탁구 | 수영 | |
|---|---|---|---|
| 석환 | 40 | 10 | 10 |
이렇게 가로로 한줄씩, 종목의 갯수(n이라하자)만큼 뽑은 배열을 구한다음 그것에 (0,0), (1,1), (2,2,)..(n-1,n-1)을 뽑으면 모든 경우의 수를 구해보는 것과 같다
이해하기 위해 표로 다시 표현하자면
| 테니스 | 탁구 | 수영 | |
|---|---|---|---|
| 석환 | 40 | 10 | 10 |
| 영재 | 20 | 5 | 0 |
| 인용 | 30 | 30 | 30 |
| 정현 | 70 | 0 | 70 |
| 준모 | 100 | 100 | 100 |
이렇게 종목 수인 3개 만큼 뽑는 모든 경우의 수를 순서를 고려하여 구한 다음 그중 능력치가 최대인 값을 찾으면 된다.
위 예시에서는 5개중 3개를 순서를 고려하여 뽑으니 5P3이 된다.
그렇게 구한 5P3=60개의 순서를 하나식 순회해서 종목의 갯수, 즉 여기서는 3개이므로 (0,0),(1,1),(2,2)를 모든 경우에 대해 고른다면, 결국 모든 경우를 구하는 것과 같다
문제에서 얻은 것
| 테니스 | 탁구 | 수영 | |
|---|---|---|---|
| 석환 | 40 | 10 | 10 |
| 영재 | 20 | 5 | 0 |
| 인용 | 30 | 30 | 30 |
| 정현 | 70 | 0 | 70 |
| 준모 | 100 | 100 | 100 |
이러한 2차원 테이블에서 서로다른걸 선택하는 경우를 고려할 경우,
일반적으로 세로로, 즉 여기서는 종목별로 하나식 고려해보는게 일반적이지만,
가로로, 즉 여기서는 사람(선수)별로 하나식 골라보는 경우도 생각해볼수 있다.
가로든 세로든 상관없다. 생각에 제한을 두지 말자. 자유롭게 데이터를 가지고 놀수 있어야한다