[c++] Programmers - PCCP 모의고사 1회 2번 체육대회

PCCP 모의고사 1회 2번
[PCCP 모의고사 #1] 체육대회

9월 18일 일요일 PCCP 준비를 위해 모의고사를 풀어보는중
알 것 같은 문제의 구현이 어려워서 고민하고있는데
예지 언니가 이거 "N퀸 아니야?" 라고 하는것이다....
와 라피신 코드 바로 뒤져서 풀었다!! 이 언니는 천재야 언니 생일축하해^^

대표를 뽑는 문제이다. 다만 2차원 배열이라 조합에 어려움을 느낄 수 있다.

백준 9663 N-Queen

https://www.acmicpc.net/problem/9663

유사한 문제를 첨부한다.
N-Queen을 푼 사람이라면 바로 감을 잡을 수 있을것이다. == 먼저 풀고와라.
라피신때 코드가 도움이 되다니요 역시 42서울은 내 인생에 도움이 된다니까

Solution

dfs를 이용하여 index를 오른쪽으로 옮겨갈 것이다. 한 경우를 모두 다 찾았으면 최댓값을 갱신해준다.
이 때, 한 사람을 중복으로 체크하지않도록 v 배열을 만들어 체크하였다.

2차원 vector 함수 전달

보낼때

int solution(vector<vector<int>> ability) {
    dfs (ability,0);

받을때

void dfs(vector<vector<int>> &ability, int index){

근데 이 전달방법은 Call by Value라고 한다. Call by Reference를 하려면 &를 빼면 된다고 하는 것 같은데, 더 찾아보겠다.

수행시간

뿌듯!!

소스 코드

#include <string>
#include <vector>

using namespace std;

int v[10] = {0,};
int mymax = 0,sum = 0;

void dfs(vector<vector<int>> &ability, int index){
    
    if (index == ability[0].size()){ //한 경우를 다 찾았으면 합산
        if (mymax < sum)
            mymax = sum;
        return ;
    }
    
    for (int i=0; i<ability.size(); i++){
        if (v[i] == 1)
            continue;
        v[i]=1;
        sum += ability[i][index];
        dfs(ability,index+1);
        sum -= ability[i][index];
        v[i]=0;
    }
}

int solution(vector<vector<int>> ability) {
    int answer = 0;
    
    dfs (ability,0);
    answer = mymax;
    
    return answer;
}