C++ / 프로그래머스 / 1회 모의고사 - 체육대회

문제

 

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

프로그래머스

문제풀이

 

DFS로 문제를 풀었다. 조건을 두었기 때문에 모든 경우의 수가 아닌 (운동 종목 개수)^(운동 종목 개수)만큼만 탐색한다.

 

한 학생은 최대 한 개의 종목만 대표할 수 있고, 운동 종목 개수만큼 대표선수를 뽑아야 한다.

따라서 운동 종목별로 모든 운동 종목의 개수만큼의 학생만 따로 뽑아 그 경우의 수를 모두 찾는 식으로 풀었다.

 

만약 운동이 3가지(테니스, 탁구, 수영), 학생이 5명이라 가정해 보자.

운동 대표 선수는 총 3명이 뽑힌다.

그러면 테니스 상위 3명, 탁구 상위 3명, 수영 상위 3명을 뽑고 3x3x3을 하여 모든 경우의 수를 탐색하여 가장 높은 점수를 return 하면 된다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
vector<vector<pii>>ab;
vector<bool>visited;
int answer;
int sport_cnt;

void DFS(int sport, int score, vector<bool>visited) {
    if (sport == ab[0].size()) answer = max(answer, score);
    else {        
        for (int idx = 0; idx < sport_cnt; ++idx) {
            int student = ab[idx][sport].second;
            if (visited[student]) continue;
            visited[student] = true;
            DFS(sport + 1, score + ab[idx][sport].first, visited);
            visited[student] = false;
        }
    }
}

int solution(vector<vector<int>> ability) {
    sport_cnt = ability[0].size();
    ab = vector<vector<pii>>(sport_cnt, vector<pii>(sport_cnt, { 0,0 }));
    visited = vector<bool>(ability.size(), false);

    for (int sport = 0; sport < sport_cnt; ++sport) {
        vector<pii>scores(ability.size());
        for (int student = 0; student < scores.size(); ++student) {
            scores[student] = { ability[student][sport], student };
        }

        sort(scores.begin(), scores.end(), greater<pii>());
        for (int student = 0; student < sport_cnt; ++student) {
            ab[student][sport] = scores[student];
        }
    }

    for (int student = 0; student < sport_cnt; ++student) {
        visited[ab[student][0].second] = true;
        DFS(1, ab[student][0].first, visited);
        visited[ab[student][0].second] = false;
    }

    return answer;
}