백준 3980번 선발 명단[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 백트래킹입니다. 응용이 거의 없어 쉽게 풀이할 수 있었습니다. 백트래킹을 적용할 수 있는 판단 기준은 N이 매우 작아야 합니다. 대략적으로 N이 20 이하인 경우 백트래킹 적용이 가능합니다. 

 그런데 테스트케이스가 신경쓰여 적용을 못하시는 경우도 있을 것 같습니다. 문제에서 테스트케이스가 최대 몇 개까지 주어지는지 명시되어있지 않습니다. 보통 이런 경우에는 시간복잡도에 영향을 주지 않는다는 의미이므로 신경 쓰실 필요가 없습니다.

 

2. 문제 풀이

 func(int idx, int score)라는 함수를 선언해 재귀로 구현하여 백트래킹을 구현했습니다. idx는 포지션 번호입니다. 11명의 선수 중 0이 아니고 포지션이 결정되지 않은 선수를 선택하여 idx번 포지션을 부여하고 func(idx + 1, socre + player[i][idx])를 호출하면 됩니다. 여기서 11개의 포지션이 모두 결정되면(base condition에 도달) mx = max(mx, score)로 최댓값을 저장하는 방법으로 풀이했습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int mx{};
vector<vi> player(11, vi(11));
vb isused(11);

void func(int idx, int score) {
    if(idx == 11) {
        mx = max(mx, score);
        return;
    }

    for(int i = 0; i < 11; i++) {
        if(!isused[i] && player[i][idx]) {
            isused[i] = 1;
            func(idx + 1, score + player[i][idx]);
            isused[i] = 0;
        }
    }
}

void solve(int tc) {
    for(auto &x : player) {
        for(auto &y : x) {
            cin >> y;
        }
    }   

    mx = 0;
    func(0, 0);

    cout << mx << nl;
}

int main() {
    fastio(nullptr, false);
    int tc{};
    cin >> tc;
    for(int i = 1; i <= tc; i++) solve(i);
}

 

 

4. 제출 결과