16439치킨치킨치킨

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

(N-2)+2(N-3)+3(N-4)+4(N-5)+5(N-6)+6(N-7)+7(N-8)+8(N-9)+9(N-10)...(N-1)(N-N)

N 30 일때 3가지 중복되지않고 무작위선택가능개수 4022 * 30명 = 120000

3가지 치킨을 고를 수 있다. 하나만 선택하거나 두개선택하거나 세개 선택하거나, 두개 선택시 중복선택하거나, 세개선택시 중복선택하거나 하는 경우도 가능하다. 문제를 보니 그렇다. 하지만 중복하지않고 3개선택하면 그걸로 다 해결이 된다. 중복되지 않고 3가지를 선택해야 한다는 의미이다.
메뉴의 종류가 6개라고 하자. 어떤 사람의 치킨에대한 선호도는 1,2,3,4,5,6 이라고 치자. 그럼 1~6 숫자들중에서 3가지를 원소로 가지는 부분집합을 중복되지 않게 만드는것부터 하면 된다.
123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456
위의 목록을 먼저 만드는 알고리즘부터 작성해야 한다

그리고 저 목록을 인덱스로 활용해야 한다. 목록의 첫번째 인덱스는 1,2,3 인것을 기억하자. 1,2,3번 메뉴를 선택했다고 가정하는것이다.

그렇다면 위의 그림에서 1번열 2번열 3번열을 선택한 것과 같다
그리고 초록색 행 번호는 회원번호 1,2,3 이다.
회원번호1 은 만족도가 3이다. 1,2,3번 메뉴에서 가장 높은 선호도가 3이니까
회원번호2 은 만족도가 4
회원3 은 3이다.
총합 10이다.

이런식으로 선택가능한 메뉴(3가지)조합을 먼저 만들고 그 메뉴에 대한 선호도를 계산해서 가장 큰 값을 저장하면 된다.

import java.io.*;

public class Main {

    static int N,M, MAX;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        int[][] inputArr = new int[N][M];

        for(int i = 0; i < N; ++i)
        {
            String[] read = br.readLine().split(" ");
            for(int j = 0; j < M; ++j)
            {
                inputArr[i][j] = Integer.parseInt(read[j]);
            }
        }

        int[] arr = new int[3];
        boolean[] visited = new boolean[M];

        search(0, arr, visited, inputArr);

        System.out.println(MAX);
    }

    public static void search(int level, int[] arr, boolean[] visited, int[][] inputArr)
    {
        if(level == 3)
        {
            int maxOfPerson;
            int sum = 0;
            for(int i = 0; i < N; ++i)
            {
                maxOfPerson = Integer.MIN_VALUE;
                for(int j = 0; j < arr.length; ++j)
                {
                    maxOfPerson = Math.max(maxOfPerson, inputArr[i][arr[j]]);
                }
                sum += maxOfPerson;
            }
            MAX = Math.max(sum, MAX);
            return;
        }

        for(int i = arr[level==0 ? 0 : level-1]; i < M; ++i)
        {
            if(visited[i] == false)
            {
                arr[level] = i;
                visited[i] = true;
                search(level+1, arr, visited, inputArr);
                visited[i] = false;
            }

        }
    }
}