[Algo] 백준 3980 선발 명단 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/3980

메모리 : 15732KB

시간 : 164ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] check;
    static int[][] arr;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < TC; tc++) {
            arr = new int[12][12];
            check = new int[12];
            ans = 0;
            for (int i = 1; i <= 11; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= 11; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            pick(1, 0);
            sb.append(ans).append("\n");
        }
        System.out.print(sb);

    }

    private static void pick(int num, int sum) {
        if (num >= 12) {
            ans = Math.max(ans, sum);
            return;
        }
        for (int i = 1; i < 12; i++) {
            if (arr[num][i] != 0 && check[i] == 0) {
                check[i] = 1;
                pick(num + 1, sum + arr[num][i]);
                check[i] = 0;
            }
        }
    }
}

풀이

11*11배열을 순회하면서 최댓값을 구하는 문제.

1. 능력치가 0인 포지션은 갈 수 없기때문에, 능력치를 가진 포지션만 선택한다.
2. 선수(num)이 해당 포지션을 선택했으면 check배열에 선택했음을 표시해 다른 선수와의 중복을 막는다.
3. 11명의 선수를 모두 선발한 후 (num==11) sum의 최댓값을 ans에 저장한다.