문제 탐색하기

입력 자료 정리

1. T는 테스트 케이스의 개수다
2. 이어서 들어오는 11 x 11 크기의 입력은 각 선수별로 포지션에서의 능력치이다

해결방법 추론

1. 11^11이면 백트래킹으로 힘들것이라 생각했는데 놀랍게도 0을 건너뛸 수 있고,
   적합한 포지션의 수가 최대 5개라고 하였기에 11^5로 줄어든다
2. 따라서 백트래킹으로 탐색한 다음, 모든 경우의 수를 다 구해서 리스트에 담고
   내림차순으로 정렬하여 맨 앞값을 출력한다면 될 것이라고 생각했다

시간복잡도 계산

1. 시간복잡도는 앞서 말한 11 ^ 5의 연산이 될 것이다
2. 따라서 시간복잡도는 O(11^5)이고 시간 제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. T는 int형 변수에 보관하며 각 입력값들은 11 x 11크기의 int형 2차원 배열에 보관한다
2. 이어서 출력값을 위한 리스트와 방문 체크를 위한 11크기의 1차원 boolean 타입의 배열을
   선언한다

백트래킹 설계

함수식

• void backtracking(int depth, int sum)

1. 종료를 위한 depth와 정답을 위한 sum을 파라미터로 받는다.
2. 능력치의 합을 구하는 것이므로 sum만을 파라미터로 선언하였다

재귀식

• backtracking(depth+1, sum + arr[i][depth])

1. 종료를 위해 depth를 증가시키며, 현재 포지션 depth에서 i 선수의 능력치를 sum에 더해서 넘겨준다

base condition

• if(depth == 11) {...}

1. 11이 되면 모든 포지션에서 탐색한 것이므로 list에 합산된 sum을 넣어주고 종료한다

2. 한가지 주의할점이 11만큼 순회하면서 미방문 했을 때 백트래킹을 해주는데
   이때 arr[i][depth]가 0이 아닐 때, 재귀식을 실행시키도록 해야한다

3. 이렇게 조건을 추가로 걸어주지 않으면 11^11의 연산이 발생하므로 시간제한을 초과할 것이다

출력 설계

1. 완성한 리스트를 내림차순 정렬 해준다
2. 이어서 리스트의 첫번째 인덱스 값을 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공)

import java.io.*;
import java.util.*;

public class Main {

    static int[][] arr = new int[11][11];
    static boolean[] visited;
    static List<Integer> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < 11; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int k = 0; k < 11; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            list = new ArrayList<>();
            visited = new boolean[11];
            backtracking(0, 0);
            list.sort(Collections.reverseOrder());
            bw.write(list.get(0)+"\n");
        }

        br.close();
        bw.close();
    }

    private static void backtracking(int depth, int sum) {
        if(depth == 11){
            list.add(sum);
            return;
        }

        for (int i = 0; i < 11; i++) {
            if(!visited[i] && arr[i][depth] != 0){
                visited[i] = true;
                backtracking(depth+1, sum + arr[i][depth]);
                visited[i] = false;
            }
        }

    }
}

문제 링크

3980번 - 선발 명단