PickTeam

Code

import java.util.Arrays;

public class PickTeam

{

    int n, bestSum;

    int[] team;

    int[][] nums;

    String[] names, bestTeam;

    void recur(int idx, int size) {

        if(size == team.length) {

            int sum=0;

            for(int i=0; i < team.length; i++)

                for(int j=i+1; j < team.length; j++)

                    sum += nums[team[i]][team[j]];

            if(sum > bestSum) {

                bestSum = sum;

                for(int j=0; j < team.length; j++)

                    bestTeam[j] = names[team[j]];

            }

            return;

        }

        for (int i=idx; i < n; i++) {

            if(team.length-size+i-1 == n) break;

            team[size] = i;

            recur(i+1, size+1);

        }

    }

    public String[] pickPeople(int teamSize, String[] people) {

        n = people.length;

        bestSum = Integer.MIN_VALUE;

        team = new int[teamSize];

        nums = new int[n][n];

        names = new String[n];

        bestTeam = new String[teamSize];

        for (int i=0; i < n; i++) {

            String[] s = people[i].split(" ");

            names[i] = s[0];

            for(int j=1; j < s.length; j++)

                nums[i][j-1] = Integer.parseInt(s[j]);

        }

        recur(0,0);

        Arrays.sort(bestTeam);

        return bestTeam;

    }

}

Explanation

순서에 상관없이 자신과 상대방에 대한 평가 점수를 더해나가면 된다. 처음에는 team[] 을 recur 함수에 인자로 넣었는데 스택 낭비인 것을 깨닫고 전역 배열로 선언해서 대입하였다.

 

recur() - > if(team.length-size+i-1 == n) break;

// 선택하려는 인원이 TeamSize 보다 적을 경우 반복문을 탈출한다.