백준 16439[자바] java 치킨치킨치킨

문제 링크:https://www.acmicpc.net/problem/16439

16439번: 치킨치킨치킨

▶문제

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

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

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

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

▶입력

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

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

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

▶출력

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

▶해설

DFS를 이용한 브루트 포스로 접근할 수 있습니다. 조건을 살펴보겠습니다.

 

1. N명의 회원이 있고, M개의 치킨 종류에 대한 각각의 선호도가 있다.

2. 치킨 시키는 데 걸리는 시간을 줄이기 위해 최대 3종류의 치킨만 시킨다. 

3. 최댓값을 구해라.

 

풀이는 간단합니다. 3개의 치킨을 고른 후 각 멤버에 대해서 고른 치킨들의 최댓값을 선택해주시면 됩니다. 

 

고른 치킨을 담는 boolean 배열을 이용합니다. 

start는 앞에서 선택을 했던 것은 더 이상 선택하지 않도록 하기 위해 다음에 넘길 때 i+1로 진행합니다.  

for(int i=start; i<m; i++){
    if(!check[i]){
        check[i]=true;
        dfs(i+1, depth+1);
        check[i]=false;
    }
}

 

depth==3 즉 3개의 치킨을 고른 상태입니다.

n명에 대해서 각 최댓값을 구합니다. check [j] ==true라면 고른 치킨이므로 멤버에 대한 최댓값을 구한 후 더해줍니다. 

if(depth==3){
    int sum=0;
    for(int i=0; i<n; i++){
        int temp=0;
        for(int j=0; j<m; j++){
            if(check[j]){
                temp = Math.max(temp, map[i][j]);
            }
        }
        sum+=temp;
    }
    result = Math.max(sum,result);
    return;
}

 

전체 코드 

import java.io.*;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.time.LocalDateTime;
import java.util.*;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;


public class Main {


    static int n,m;
    static int result;
    static int[][]map;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        map = new int[n][m];

        check = new boolean[m];
        for(int i=0; i<n; i++){
            String[] s1 = br.readLine().split(" ");
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(s1[j]);
            }
        }

        dfs(0,0);

        System.out.println(result);
    }
    private static void dfs(int start, int depth){
        if(depth==3){
            int sum=0;
            for(int i=0; i<n; i++){
                int temp=0;
                for(int j=0; j<m; j++){
                    if(check[j]){
                        temp = Math.max(temp, map[i][j]);
                    }
                }
                sum+=temp;
            }
            result = Math.max(sum,result);
            return;
        }

        for(int i=start; i<m; i++){
            if(!check[i]){
                check[i]=true;
                dfs(i+1, depth+1);
                check[i]=false;
            }
        }
    }
}