[C++/PGS] [PCCP 모의고사 #1] 2번 - 체육대회

 

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

프로그래머스

---

프로그래머스 PCCP 모의고사 1회 - 2번

소요시간 약 23분

순열(permutation) 혹은 dfs/재귀 유형, 추정 난이도는 level 2-3

 

내가 C++을 좋아하는 이유,,, 
순열같은 기본 알고리즘 구현 부담을 줄여주는 표준 함수가 풍부하다!!

 

표준 라이브러리 중 <algorithm> next_permutation 함수를 사용해서 해결하였다.

⚠️ 순열 함수 사용시에는 반드시 정렬 후, do~while 반복문으로 써줘야 한다.

그리고 이 문제에서는 ability 벡터를 reverse해줘야 함 (운동종목 기준으로 순열 처리하기 위해서)

 

 

나의 풀이

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

int solution(vector<vector<int>> ability) {
    int answer = 0;
    // 최댓값, 그리디? 각 종목별로 순서 다르게
    int students = ability.size();
    int sports = ability[0].size();
    vector<vector<int>> reverse;
    // 순열을 위해 벡터 뒤집기
    for(int i=0; i<sports; ++i){
        vector<int> v;
        for(int j=0; j<students; ++j) v.push_back(ability[j][i]);
        reverse.push_back(v);
    }
    // 순열 활용해서 모든 경우의 수 탐색
    sort(reverse.begin(), reverse.end());
    do{
        vector<vector<int>> abt = reverse;
        int maxSum = 0;
        
        for(int i=0; i<sports; ++i){
            int maxAb = 0;
            int maxIdx = 0;
            for(int j=0; j<students; ++j){
                if(maxAb < abt[i][j]) {
                    maxAb = abt[i][j];
                    maxIdx = j;
                }
            }
            maxSum += maxAb;
            for(int k=0; k<sports; ++k){
                abt[k][maxIdx] = 0;
            }
        }
        if(answer < maxSum) answer = maxSum;
    }while(next_permutation(reverse.begin(), reverse.end()));
    
    return answer;
}

 

모의고사 1회는 3번 제외하고 다 해결했다.

3번은.....수학 문제인데 못 풀겠다 ㅠㅠ 힌트 얻어야 할듯