[ BOJ ][JAVA][16439] 치킨치킨치킨

www.acmicpc.net/problem/16439

16439번: 치킨치킨치킨

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	331	240	214	74.825%

문제

N명의 고리 회원들은 치킨을 주문하고자 합니다.

치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.

시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.

진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.

두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.

i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., a**i,M (1 ≤ ai,j ≤ 9) 가 주어집니다.

출력

첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.

예제 입력 1

3 5
1 2 3 4 5
5 4 3 2 1
1 2 3 2 1

예제 출력 1

13

예제 입력 2

4 6
1 2 3 4 5 6
6 5 4 3 2 1
3 2 7 9 2 5
4 5 6 3 2 1

예제 출력 2

25

코드

import java.util.*;
import java.io.*;
public class p16439 {
    static int n, m, max;
    static int[][] member;
    static int[] chicken;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visit = new boolean[m];
        member = new int[n][m]; // 총 멤버의 치킨 선호도 표
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                member[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        max = 0;
        comb(0, 0);
        System.out.println(max);
    }

    static void comb(int start, int depth) {
        if (depth == 3) {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int sat = 0;
                for (int j = 0; j < m; j++) {
                    if (visit[j]) {
                        sat = Math.max(sat, member[i][j]);
                    }
                }
                sum += sat;
            }

            max = Math.max(max, sum);
            return;
        }

        for (int i = start; i < m; i++) {
            if(visit[i]) continue;
            visit[i] = true;
            comb(i, depth + 1);
            visit[i] = false;
        }
    }
}