SWEA 2115. [모의 SW 역량테스트] 벌꿀채취

Link
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&problemTitle=%EC%97%AD%EB%9F%89&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

---

내가 제출한 코드

import java.util.*;
import java.io.*;

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int n, m, c, answer;
    
    static boolean[] v;
    
    static int[] personA = new int[2];
    static int[] dataA = new int[2];

    static int[] personB = new int[2];
    static int[] dataB = new int[2];

    static int[][] map;

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine());
        for (int i = 1; i <= t; i++) {
            init();
            run();
            sb.append("#").append(i).append(" ").append(answer).append("\n");
        }
        System.out.print(sb);
    }

    private static void init() throws Exception {
        answer = 0;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = new boolean[m];
        c = Integer.parseInt(st.nextToken());

        map = new int[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());
            }
        }
    }

    private static void run() {
        // 1번 사람 좌표 뽑기
        findA();
    }

    private static void findA() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n - m; j++) {
                personA[0] = i;
                personA[1] = j;
                
                dataA = new int[2];
                v = new boolean[n];
                // 최대값 구하기
                recur(personA, dataA, 0, 0);
                // 2번 사람 좌표 뽑기
                findB();
            }
        }
    }

    private static void findB() {
        for (int i = personA[0]; i < n; i++) {
            // 같은 행에서 뽑는 경우
            if (i == personA[0]) {
                for (int j = personA[1] + m; j <= n - m; j++) {
                    personB[0] = personA[0];
                    personB[1] = j;
                }
            }
            // 다른 행에서 뽑는 경우
            else {
                for (int j = 0; j <= n - m; j++) {
                    personB[0] = i;
                    personB[1] = j;
                }
            }
            // 사용되는 데이터들 초기화
            dataB = new int[2];
            v = new boolean[n];
            // 최대값 구하기
            recur(personB, dataB, 0, 0);
            // 값 갱신하기.
            if (answer < dataA[0] + dataB[0]) {
                answer = dataA[0] + dataB[0];
            }
        }
    }

    private static void recur(int[] person, int[] data, int cost, int nowC) {
        // 최대로 수학 가능한 범위 = c
        if (nowC > c) {
            return;
        }
        // 값 갱신하기
        if (cost > data[0]) {
            data[0] = cost;
            data[1] = nowC;
        }
        // 재귀 
        for (int i = person[1]; i < person[1] + m; i++) {
            if (!v[i]) {
                v[i] = true;
                int nowValue = map[person[0]][i];
                recur(person, data, cost + (int) Math.pow(nowValue, 2), nowC + nowValue);
                v[i] = false;
            }
        }
    }
}

---

생각해낸 로직

1. 첫번째 사람의 좌표 세팅

2. 두번째 사람의 좌표 세팅 ( 같은 행에서 뽑는 경우의 좌표값을 유의한다. )

3. 사람마다 세팅된 좌표값 내에서 가능한 최대값을 확인한다. ( C의 값을 넘지 않으면서 최대값 )

4. 두 사람의 최대값의 합의 최대값이 Answer이다.