[백준 03980] 선발 명단 [Java]

문제

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

 

---

풀이

11명의 선수들이 각 포지션에서의 적합한 능력치를 바탕으로 모든 포지션에 배치했을 떄, 선수들의 최대 능력치 합을 구하는 문제다.

완전 탐색을 통해 충분히 구할 수 있으나, 여러 TC가 존재하기 때문에 최적화를 진행해야 한다.

한 선수는 11개 중 최대 5개의 포지션에 대한 능력치를 가질 수 있다.

따라서 능력치가 0보다 큰 경우에 대해서만 탐색하면 된다.

    private static int bt(int sum, int i) {
        if (i == 11) {
            return sum;
        }
        int res = 0;
        for (int j = 0; j < 11; ++j) {
            if (!visited[j] && A[i][j] > 0) {
                visited[j] = true;
                res = Math.max(res, bt(sum + A[i][j], i + 1));
                visited[j] = false;
            }
        }
        return res;
    }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/03980.java