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

생각

두명의 사람이 벌꿀을 채취하려고한다.
각 사람은 [N][N] 배열에서 가로로 이어져있는 M 칸을 선택할 수 있는데, 두 사람이 고른 칸이 1칸이라도
중복이되어서는 안된다.
칸을 골랐으면 각자 주어진 C만큼 벌꿀 채취가 가능하다. 아래와 같이 주어진 벌꿀 판에서 C=13이고
M=2일 경우 최대 이득은 174가 된다.

위를 봐서는 모든 칸을 계산 하는 것 같지만 아래와 같이 주어진 C를 넘기지 않는 선에서
최대 값을 구하여야한다.
N,M,C와 배열이 주어졌을 경우 최대값을 출력하라.

처음 생각

주어진 배열에서 조건에따른 최대값을 찾아야한다. 따라서 별다른 생각이 나지 않아 완전 탐색을 하였다.

▶ 조건이 행으로만 M칸 진행으로 주어졌기 때문에 각 행별로 M칸씩 모든 경우를 살펴보았다.

▶ 주어진 N이 최대 10이므로 최대 크기가 100인 배열에서 한 개씩 선택하여 그 칸에대해 M칸씩 살펴보면서 찾아볼 경우 M이 1이라하더라도 대략 100(칸 선택)x100(M칸 살펴보기) = 10000 최악의 경우에도 만개 밖에 되지 않으므로 주어진 3초라는 시간안에 충분한 처리가 가능하다.

다음 생각

행을 개별적으로 보면서 각 행의 0 열 부터 M칸을 살펴보았다.

▶ 완전 탐색이므로 M칸을 살펴본 후, 그 칸에서 만들 수 있는 가장 큰 수를 getMax() 메소드를 만들어 DFS 탐색을 통해 구하였고, 구한 Max 값과 해당 칸의 x좌표와 시작 y 좌표를 inner class Pair의 생성 매개 변수로 사용하여 저장하기 위해 만들어둔 List에 넣어주었다.

다다음 생각

이러한 방식으로 모든 칸에대해 구한 Max 값들을 같은 방식으로 solve2() 메소드를 만들어 DFS 탐색을 통해 2개의 최대값을 구해주었다.

▶ 주의해야 할 점은 칸이 겹치면 안되므로 해당 값의 (x,y)에 대해 M칸을 사용했다는 처리를 한 후 넘겨주어야한다. 그리고 현재 자신의 좌표로 부터 M칸 중에 방문처리가 되어있다면 건너뛰고 다음 걸 검사하도록 하였다.

방안

1) 주어진 숫자가 작다면 이리저리 생각하는 것보다 완전 탐색을 통한 풀이가 정확하며, 생각을 덜 할 수 있다.

2) 댓글을 보니 실제 데이터가 부실하다는 말이 있었는데 완전 탐색을 이용해서 댓글에서 주어진 몇 개의 Input도 잘 됐다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int n,m,c;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken()); // 채취 가능 벌통 수(연속)
            c = Integer.parseInt(st.nextToken()); // 담기 가능 제한 수
            arr = new int[n][n];
            for(int j=0;j<n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<n;k++)
                    arr[j][k] = Integer.parseInt(st.nextToken());
            }
            
            visited = new boolean[n][n];
            list = new ArrayList<>();
            max = 0;
            // 열은  n-m만큼만 진행 해주면 된다.
            for(int j=0;j<n;j++) {
                for(int k=0;k<=n-m;k++)
                    solve(j,k);
            }
            result = 0;
            // list 안에 들어간 값들로 Max값 찾기
            solve2(0,0,0);
            sb.append("#"+i+" "+result+"\n");
        }
        System.out.print(sb);
    }
    
    static int result;
    static boolean[][] visited;
    private static void solve2(int idx,int sum,int cnt) {
        // getMax와 동일한 방식으로 모든 조건을 살펴 Max값을 찾아주자.
        if(cnt==2) {
            result = Math.max(result, sum);
            return;
        }
        // idx를 넘을경우 return
        if(idx>=list.size()) return;
        
        int x = list.get(idx).x;
        int y = list.get(idx).y;
        
        boolean flag = false;
        for(int i=y;i<y+m;i++) {
            if(visited[x][i]) {
                flag = true;
                break;
            }
        }
        if(flag) {
            // 해당 index가 포함 안되도 다음걸로 넘겨는 주기.
            solve2(idx+1,sum,cnt);
            return;
        }
        
        // 겹치지 않는다면 겹침 체크해주기
        for(int i=y;i<y+m;i++)
            visited[x][i] = true;
        // 자신 포함
        solve2(idx+1,sum+list.get(idx).value,cnt+1);
        // 이제 사용안하므로 겹침 체크 풀어주기
        for(int i=y;i<y+m;i++)
            visited[x][i] = false;
        // 자신 미포함
        solve2(idx+1,sum,cnt);
    }
    
    // 최대 값을 찾아라? -> 모든 경우의 수를 따져보자
    static int max;
    static List<Pair> list;
    private static void solve(int x,int y) {
        // 한 줄씩 m칸으로 만들 수 있는 모든 경우의 수를 찾고 List에 넣어주기
        
        // m 칸씩 살펴보므로 index를 초과하면 종료 
        if(y+m>n) {
            return;        
        }
        // 선택할 칸 체크
        int[] tArr = new int[m];
        // m 개만큼 넣기
        for(int i=y,idx=0;i<y+m;i++)
            tArr[idx++] = arr[x][i];
        // 얻은 m개 값으로 모든 조건을 따져서 가장 큰값 구해주기
        tSum=0;
        getMax(tArr,0,0,0);
        list.add(new Pair(tSum, x, y));
    }
    
    static int tSum;
    private static void getMax(int[] tArr,int idx,int sum,int sSum) {
        // 끝까지 살펴봤으면 종료
        if(idx==m) {
            tSum = Math.max(tSum, sSum);
            return;
        }
        // c보다 작다면 해당 index 포함
        if(sum+tArr[idx]<=c) {
            getMax(tArr, idx+1, sum+tArr[idx], sSum+tArr[idx]*tArr[idx]);
        }
        // 해당 index 미포함
        getMax(tArr,idx+1,sum,sSum);
    }
    
    static class Pair{
        private int value,x,y;
        public Pair(int value,int x,int y) {
            this.value = value;
            this.x = x;
            this.y = y;
        }
    }
}