프로그래머스 PCCP모의고사 1회 2번 체육대회 c++

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

프로그래머스

dfs를 돌면서 최적의 경우를 찾으려 했으나.. 다음 재귀스택에서 가장 큰 것만 찾는 로직으론 최대합을 찾을 수 없다는 걸 깨달았다.

#include <string> // 실패코드
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> abil;
int compNum;
int playNum;
int answer = 0;

void dfs(int depth, int sum, vector<vector<int> > ability) {
    if (depth == compNum) {
        answer = min(sum, answer);
        return ;
    }
    int curScore = -1;
    int maxPlayer = -1;
    for (int i = 0; i < playNum; i++) {
        if (ability[i][depth] > curScore) {
            curScore = ability[i][depth];
            maxPlayer = i;
        }
    }
    for (int i = 0; i < playNum; i++)
        ability[maxPlayer][i] = -1;
    dfs(depth + 1, sum + curScore, ability); // 아 이거 안된다 완전탐색으로 해야한다...
}

int solution(vector<vector<int>> ability) {
    compNum = ability.size(); // 대회 횟수
    playNum = ability[0].size(); // 선수 인원
    abil = ability;
    
    dfs(0, 0, ability);
    return answer;
}

진자 시험이였으면 30분 날린 것... 문제 이해와 구상 하는 시간을 더 늘리자.

 

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

int solution(vector<vector<int>> ability) {
    int compNum = ability[0].size(); // 대회 횟수
    int playNum = ability.size(); // 선수 인원
    int answer = -1;
    vector<int> v;
    for (int i = 0; i < playNum; i++)
        v.push_back(i);
    do {
        int curSum = 0;
        for (int i = 0; i < compNum; i++)
            curSum += ability[v[i]][i];
        answer = max(curSum, answer);
    }
    while (next_permutation(v.begin(), v.end()));
    return answer;
}

순열 완전탐색으로 날먹