[SWEA]#2115 벌꿀채취

문제

(SWEA#2115)모의 역량 테스트 - 벌꿀채취

풀이

이 문제는 먼저 가능한 벌꿀 채취를 모드 구해서 ArrayList에 넣고 이 중 2개를 선택해서 벌꿀채취가 최대가 되는 경우를 구했다. 그 과정에서 조합을 두번 이용했다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Arrays;
 
class Solution
{
    static int N;
    static int M;
    static int C;
    static int[][] map;
    static ArrayList<Pair> list;
    static int max;
    static int nsum;
     
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            String[] input = br.readLine().split(" ");
            N = Integer.parseInt(input[0]);
            M = Integer.parseInt(input[1]);
            C = Integer.parseInt(input[2]);
            map = new int[N][N];
            max = -1;
             
            for(int i=0; i<N; i++) {
                input = br.readLine().split(" ");
                for(int j=0; j<N; j++) {
                    map[i][j] = Integer.parseInt(input[j]);
                }
            }
             
            list = new ArrayList<>();
            for(int i=0; i<N; i++) {
                for(int j=0; j<=N-M; j++)
                    list.add(new Pair(i, j));
            }
            boolean[] selected = new boolean[list.size()];
            Pair[] ans = new Pair[2];
            combin(selected, ans, 0, 0);
            System.out.println("#"+test_case+" "+max);
        }
    }
     
    public static void combin(boolean[] selected, Pair[] ans, int idx, int index) {
        if(index==2) {
            //if(ans[0].x!=ans[1].x || (ans[0].x==ans[1].x) && (ans[0].y+M<=ans[1].y))
            if(ans[0].x!=ans[1].x )
                sol(ans);
            return ;
        }
         
        for(int i=idx; i<list.size(); i++) {
            if(!selected[i]) {
                selected[i] = true;
                Pair p = list.get(i);
                ans[index] = new Pair(p.x, p.y);
                combin(selected, ans, idx+1, index+1);
                selected[i] = false;
            }
        }
    }
     
    public static void get_honey(boolean[] selected, int[] arr, int idx, int c, int sum) {
        if(c>C) return;
        if(c<=C)
            nsum = Math.max(nsum, sum);
         
        for(int i=idx; i<M; i++) {
            if(!selected[i]) {
                selected[i] = true;
                get_honey(selected, arr, idx+1, c+arr[i], sum+arr[i]*arr[i]);
                selected[i] = false;
            }
        }
    }
     
    public static void sol(Pair[] honey) {
        int h = 0;
        int sum = 0;
        int[] arr = new int[M];
        boolean[] selected = new boolean[M];
         
        for(int i=0; i<M; i++) {
            int x = honey[0].x;
            int y = honey[0].y+i;
            h += map[x][y];
            arr[i] = map[x][y];
        }
         
        if(h>C) {
            nsum = 0;
            get_honey(selected, arr, 0, 0, 0);
            sum += nsum;
        }
         
        else {
            for(int i=0; i<M; i++)
                sum += Math.pow(arr[i], 2);
        }
       
        h = 0;
        arr = new int[M];
         
        for(int i=0; i<M; i++) {
            int x = honey[1].x;
            int y = honey[1].y+i;
            h += map[x][y];
            arr[i] = map[x][y];
        }
         
        if(h>C) {
            selected = new boolean[M];
            nsum = 0;
            get_honey(selected, arr, 0, 0, 0);
            sum += nsum;
        }
         
        else {
            for(int i=0; i<M; i++)
                sum += Math.pow(arr[i], 2);
        }
         
        max = Math.max(max, sum);
    }
     
    public static class Pair {
        int x;
        int y;
         
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}