[프로그래머스] 체육대회 (PCCP 모의고사 #1 2번)

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

프로그래머스

프로그래머스 - 체육대회(PCCP 모의고사 #1 2번)

문제 유형 : 순열/조합

문제 난이도 : Level 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 함수를 완성하시오.

 

풀이

n명의 학생과 m개의 종목이 있다고 하자.

순열을 통해서 모든 경우의 수를 만들어서 가장 큰 경우를 반환시키면 된다.

어차피 학생 수는 최대 10명이니 말이다.

 

순열로 학생들을 줄 세운다음, i번째 학생의 i번째 종목 점수들을 m번 누적시키면 능력치의 값을 구할 수 있고,

모든 경우에 대해서 비교해서 가장 큰 값을 반환해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int solution(vector<vector<int>> ability) {
    const int n = ability.size();
    const int m = ability[0].size();
    vector<int> students(n);
    
    int maxAbility = -1;
    
    for(int i = 0; i < n; i++) {
        students[i] = i;
    }
    
    do {
        int abil = 0;
        for(int i = 0; i < m; i++) {
            abil += ability[students[i]][i];
        }
        maxAbility = max(maxAbility, abil);
    }while(next_permutation(students.begin(), students.end()));
    
    return maxAbility;
}