[프로그래머스/ PCCP 모의고사 1] 2.체육대회

문제 내용

각 종목별 중복되지 않는 대표 학생을 뽑고, 그 대표학생들의 종목별 점수를 합했을때 최대값을 구하는 문제

 

풀이

대표적으로 dfs 를 이용하는 문제이다.

모든 값들을 다 구하고 그 값들의 최대값을 구하는 문제

아직도 어렵다...

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool visit[10] = {false,};
int _max = 0;
int sum = 0;

void dfs(vector<vector<int>>& ability, int index)
{
    if(index == ability[0].size())
    {
        if( _max < sum)
        {
            cout << sum << endl;
            _max = sum;
        }
        return;
    }
    
    for(int i = 0; i < ability.size(); i++)
    {
        if( visit[i] == true )
            continue;
        visit[i] = true;
        sum += ability[i][index];
        dfs(ability, index+1);
        sum -= ability[i][index];
        visit[i] = false;
    }
}


int solution(vector<vector<int>> ability) {
    int answer = 0;
    
    dfs(ability, 0);
    answer = _max;
    
    return answer;
}