[ Baekjoon - 09/13 ] - 16439번: 치킨치킨치킨

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

16439번: 치킨치킨치킨

 

• 소요 시간 : 2시간 5분

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초 
     • 메모리 : 128MB
   • 문제
     • N명(1≤N≤30)의 회원, 치킨의 종류는 M개(3≤M≤30)
     • 회원마다 특정 치킨의 선호도(ai,1, ai,2, ..., ai,M (1 ≤ ai,j ≤ 9)) 존재
     • 회원의 만족도는 주문한 치킨의 가장 큰 선호도값
     • 목적 : 최대 3가지 종류의 치킨을 시킬때, 회원들의 만족도 합이 최대가 되도록 => 만족도의 합 최댓값 도출 
   • 이해
     • 3개의 치킨을 선택했을때, 겹치지않게 고른 MAX선호도의 합중 가장 큰값을 찾는 문제
2. 문제를 익숙한 용어로 재정의와 추상화
   • 
   • 위 그림처럼 N명의 사람을 나타내는 m0~mN-1(man의 약자로 m을 했지만 M변수가 존재하므로 딴걸 쓰는게 좋았을듯 하다), M종류의 치킨(ch1~chM), 그리고 각 선호도(a0,1 ~ aN-1,M)을 나타내었다.
   • 각 최댓값을 가정해보았고, 그랬을때 어떻게 선택되는지를 그림으로 나타내 보았다. 
3. 문제를 어떻게 해결할 것인가
   • 
   • 1st 접근)
     사실 처음에 문제를 잘못이해해서 완전탐색이 필요하다고 생각했다.
     => Max이면 값을 그대로, Max가 아닌 값은 0으로 설정한 2차원배열(map)을 먼저 만든다. DFS를 돌리는데, 값이 0이거나 방문한 행/열이면 지나가고 아니라면 선택하는식으로 재귀를 이용해 돌리고자 했다. 혹은 이중반복문을 통해 Max값을 담은 배열을 하나 만들어서 중복제거 및 최댓값만 저장하고자 했다.
     ※ ch2의 선호도가 a1과 a2가 같을 때, ch3의 선호도가 a2라면, 무조건 ch2는 a1을 선택해야한다고 생각했기 때문에 생긴 착오였다...ㅠㅠ 
   • 2nd 접근)
     위 생각을 바로잡고나니 해당부분에서는 dfs가 필요없고, 입력값을 넣은 map에서 바로 조합을 쓰면 된다는 것을 깨달았다.
4. 위 계획을 검증
   • 1st 접근)
     입력제외 배열에서 각 행별로 Max값 추출할 때, O(N) * M
     배열에 최댓값이 아니면 0을 삽입할 때, O(MN)
     Max값만 담은 배열에 담을 때, O(NM)
     N개에서 3개를 뽑는 조합 -> NC3 = N(N-1)(N-2) / 3! => O(N^3) ※구현 전이라 이렇게 생각했다
     ==> O(NM)*3 + O(N^3) = 29700번 (너무 시도횟수가 작음을 인지했어야했다... 왜 기뻐했을까)
   • 2nd 접근)
     입력값을 받아 2차원 배열에 저장하면, O(NM)
     N개에서 3개를 뽑는 조합 구현 -> NC3 = O(M^3*(M+3)) //3이 나온 이유는 바로 밑에
     조합에서 뽑은 경우의 수의 합이 최대인지 판단 -> 1중 반복문이니 O(3)
     ==> O(NM)+O(M^3*(M+3)) = 891900번
5. 계획 수행 (실제코드 작성)
   

   import java.util.*;
   import java.io.*;
   
   public class Main{
       //1. int형 변수 N, M, result, 배열(int형 2차원 배열 map[M][N], 최댓값만 가질 int형 1차원 배열 maxList) 선언
       static int N,M,result=0;
       static int[][] map;
       static int[] combList; // maxList,
   
       public static void main(String[] args) throws IOException {
           //System.setIn(new FileInputStream("src/input.txt"));
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
           StringTokenizer st = new StringTokenizer(br.readLine());
           N = Integer.parseInt(st.nextToken());
           M = Integer.parseInt(st.nextToken());
   
           //2. 입력값을 받아 2차원 배열(map)에 저장
           map = new int[N][M];
           for (int n = 0; n < N; n++){
               st = new StringTokenizer(br.readLine());
               for (int m = 0; m < M; m++) {
                   map[n][m] = Integer.parseInt(st.nextToken());
               }
           }
   
           combList = new int[3];
   
   //        maxList = new int[N];
   
   //        //3. map을 이중반복문으로 돌며 Max를 추출하여 maxList에 저장 및 max아닌 map요소는 0으로 치환
   //        for (int n = 0; n < N; n++) {
   //            int max = 0;
   //            for (int m = 0; m < M; m++) {
   //                max = Math.max(max, map[n][m]);
   //            }
   //            maxList[n] = max;
   //            for (int m = 0; m < M; m++) {
   //                if (max != map[n][m]) {
   //                    map[n][m] = 0;
   //                }
   //            }
   //        }
   
           comb(0,0);
   
           //5. 출력
           System.out.println(result);
       }
   
       // 조합을 이용해 3개 뽑기 - 재귀
       public static void comb(int cnt, int s){
           if(cnt==3){
               int sum = 0;
               for (int n = 0; n < N; n++) {
                   sum += getMax(n);
               }
               if(sum>result)
                   result = sum;
               return;
           }
   
           for (int m = 0; m < M; m++) {
               combList[cnt] = m;
               comb(cnt+1, m+1);
           }
       }
   
       private static int getMax(int n) {
           int max = 0;
           //4. maxList를 조합을 이용해 3개를 뽑는 경우의 수만큼 반복
           for (int i = 0; i < 3; i++) {
               int tmp = map[n][combList[i]];
               //4-1. 해당 경우의 수의 max값과 이전의 max값을 비교하여 큰값을 저장
               if (tmp>max)
                   max  = tmp;
           }
           return max;
       }
   }

6. 회고하기
   • 4,5에 이어 적었다.

 

• 결과