[PCCP 모의고사] 2번 체육대회 (조합)

문제 링크

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

 

 

풀이

처음에는 완전탐색은 시간초과가 날 것 같아서 뭔가 로직을 써야하나? 생각하다 그냥 조합으로 가능성 전부 돌려서 찾았다. 

조건만 정리하면 아래와 같다.

- 각 종목마다 1명씩 대표를 뽑는다.

- 한사람당 1개의 종목만 출전한다.

 

따라서, 전체 인원들 중, 각 종목(m개) 의 대표를 중복 없이 선택하면 된다. 단, 누가 어떤 종목을 채택하는지가 중요하기에

"순서 상관있이 선택하는 조합" 으로 생각하고 코드를 구현해도 된다. 

따라서 comb라는 재귀함수를 통해 dfs 탐색으로 각 종목(depth)마다, 중복 없이 임의의 학생 1명씩을 선택하는 모든 가능성 중, 최솟값을 찾아서 리턴하면 끝이다.

 

#include <string>
#include <vector>
using namespace std;
vector<vector<int>> v;
int var, n;
int mx=-98765;
int visit[10010];
void comb(int depth,int sum){//depth ==각 종목 나타낸다. 
    if(depth==var){
        if(sum>mx)mx=sum;
        return;
    }
    for(int i=0;i<n;i++){//각 종목마다 전체 인원 중 1명을 중복없이 뽑는다.
        if(visit[i])continue;
        visit[i]=1;
        comb(depth+1,sum+v[i][depth]);
        visit[i]=0;
    }
}

int solution(vector<vector<int>> ability) {
    v=ability;
    int answer = 0;
    var=ability[0].size();
    n=ability.size();
    comb(0,0);
    return mx;
}