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

문제

https://school.programmers.co.kr/learn/courses/15008/lessons/121684?language=cpp

프로그래머스 체육대회

프로그래머스 체육대회

 

문제 내용

각 학생별로 체육 대회 특정 종목에 나갔을 때의 능력치를 담은 2차원 배열이 주어진다.

종목마다 1명의 학생이 나갈 수 있고, 각 학생은 1개의 종목에만 나갈 수 있다.

능력치의 합이 최대가 되는 경우를 구하면 된다.

 

문제 풀이

각 종목별로 누가 나갈지를 정해야 한다.

이는 백트래킹으로 쉽게 구할 수 있다.

 

코드

#include <string>
#include <vector>

using namespace std;

vector<int> studentOrder;
vector<int> used;
int ex_num;
int student;
int mmax=-1;

void decideStudent(int cnt, vector<vector<int>> &ability){
    if(cnt==ex_num){
        int ssum=0;
        for(int i=0;i<cnt;i++){
            ssum+=ability[studentOrder[i]][i];
        }
        mmax=max(mmax, ssum);
        return;
    }
    
    for(int i=0;i<student;i++){
        if(!used[i]){
            used[i]=true;
            studentOrder[cnt]=i;
            decideStudent(cnt+1, ability);
            used[i]=false;
        }
    }
}

int solution(vector<vector<int>> ability) {
    ex_num=ability[0].size();
    student=ability.size();
    
    studentOrder.assign(ex_num, 0);
    used.assign(student, 0);
    
    decideStudent(0, ability);
    
    return mmax;
}