[SW Expert Academy] 벌꿀채취 - java

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

[

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

](https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2)

public class 벌꿀채취2 {

    static int N, M, C;
    static int map[][];
    static boolean check[][];
    static int answer, maxSum;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            check = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            answer = 0;
            solve();
            System.out.println("#" + test_case + " " + answer);
        }
    }

    private static void solve() {
        int window[] = new int[M];
        numbers = new int[M];
        Integer value[] = new Integer[N];
        for(int i=0; i<N; i++) {
            max = 0;
            for(int j=0; j<N; j++) {
                if(j+M <= N) {
                    for(int k=j; k<j+M; k++) {
                        window[k-j] = map[i][k];
                    }
                    combi(0,0,window);
                }
            }
            value[i] = max;
        }
        Arrays.sort(value, Collections.reverseOrder());
        answer += value[0];
        answer += value[1];
    }

    static int numbers[];
    static int max;
    private static void combi(int cnt, int idx, int[] window) {
        int sumHoneyCnt =0; // 벌꿀 양
        int sumHoneyValue = 0;
        for(int i=0; i<cnt; i++) {
            sumHoneyCnt += window[numbers[i]];
            sumHoneyValue += window[numbers[i]] * window[numbers[i]];
        }
        if(sumHoneyCnt<=C) {
            if(max < sumHoneyValue) {
                max = sumHoneyValue;

            }
        }
        if(cnt == M) return;
        for(int i=idx; i<M; i++) {
            numbers[cnt] = i;
            combi(cnt+1, i+1, window);
        }
    }


}

소요시간 : 2시간
문제 접근을 잘못해서 많이 헤맨 문제입니다.
그리고 같은 행에서 2번 뽑아도 되고, 1번만 뽑아도 테케가 통과한다고 합니다.
저는 1번만 뽑는다고 가정하고
각 행에서 벌통의 갯수 M만큼 선택한 후 그 안에서 조합을 이용해서 최댓값을 구했습니다.
각 행의 최댓값을 내림차순으로 정렬하고 가장 큰 2개의 값을 뽑아냈습니다.