치킨치킨치킨

조소복·2022년 10월 2일

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 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

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

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

        for(int i=0;i<N;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                person[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        int result=Integer.MIN_VALUE;
        for(int i=0;i<M;i++){
            int tmp=0;
            for(int j=i;j<M;j++){
                for(int k=j;k<M;k++){
                    if(i==j || j==k || k==i) continue;
                    int sum=0;

                    int max=0;
                    //회원 수 만큼 반복
                    for(int n=0;n<N;n++){
                        //선택한 치킨 중 선호도 높은 값 선정
                        max=Math.max(person[n][i],person[n][j]);
                        max=Math.max(max,person[n][k]);
                        sum+=max;
                        max=0;
                    }

                    if(result<sum) result=sum;
                }
            }
        }

        System.out.print(result);
    }
}

문제를 잘 읽어보면 다음과 같은 순서로 로직을 짤 수 있다.

M개의 치킨 중 세 마리를 선택
각 회원별로 선택한 치킨 세 마리 중 선호도가 가장 높은 치킨의 선호도 값 합치기

치킨 세 마리라고 문제에서 정해뒀기 때문에 반복문 세 번을 돌려서 문제를 풀 수 있다.

치킨 세 마리를 선택하는데에 3중 for문 외에도 다른 방법이 있겠지만 우선은 for문을 세 번 돌리는 방식으로 구현했다.

치킨 세 마리의 선호도

int result=Integer.MIN_VALUE;
for(int i=0;i<M;i++){
    int tmp=0;
    for(int j=i;j<M;j++){
        for(int k=j;k<M;k++){
            if(i==j || j==k || k==i) continue;
            int sum=0;
            
            int max=0;
            //회원 수 만큼 반복
            for(int n=0;n<N;n++){
                //선택한 치킨 중 선호도 높은 값 선정
                max=Math.max(person[n][i],person[n][j]);
                max=Math.max(max,person[n][k]);
                sum+=max;
                max=0;
            }
            
            if(result<sum) result=sum;
        }
    }
}