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

https://school.programmers.co.kr/learn/courses/20847/lessons/255901

프로그래머스

 

최대 10명, 10과목이 있을 수 있으며 이 문제는 완전탐색 문제이다. 

 

다이나믹 프로그래밍으로 풀이해보려 했는데 적당한 점화식이 떠오르지 않았고 N이 작아 충분히 dfs 완전탐색으로 진행할 수 있을 것이라 보았다.

 

#include <string>
#include <vector>

using namespace std;
    int answer = 0;

bool visited[11];
int N, M;
vector<vector<int>> abil;
void dfs(int idx, int event ,int power){
    if(event == M || idx == N){
        answer = max(answer, power);
        
        return;
    }
    for(int i = 0; i < N; i++){
        if(visited[i]) continue;
        visited[i] = true;
        dfs(i, event + 1, power + abil[i][event]);
        visited[i] = false;
    }
}

int solution(vector<vector<int>> ability) {
    N = ability.size();
    M = ability[0].size();
    
    abil = ability;
    
    dfs(0, 0, 0);
    return answer;
}