벌꿀채집

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&&&

SW Expert Academy

알고리즘

1. DFS를 통해 벌통에서 벌꿀을 채취 할 수 있는 가장 큰 경우를 배열에 저장한다.

2. 배열에 저장된 값을 통해 두 명의 일꾼이 선택 할 수 있는 가장 큰 조합을 찾는다.

주의사항

1. 채취 할 벌통을 선택하는 과정에서 선택한 경우와 선택하지 않는 경우를 나눠줘야한다.

예를 들어 채취 할 수 있는 용량은 작은데 꿀을 채취 할 수 있는 벌통의 수가 많을 때에는 벌통에서 벌꿀을

채취 할 수 있는 경우의 수가 많다.

2. 단순히 DFS를 통해 가장 큰 값 2개만 추출 하면 된다고 생각 할 수 있지만 벌통이 겹칠 수 있다.

-> 벌꿀을 채취 할 수 있는 가장 큰 경우를 배열에 저장

구현

package algorithm;

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

class Solution_벌꿀채집
{
    static int map[][];
    static int map_price[][];
    static int index[];
    static int C,M,N;
    static int max_subset;

    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            N = Integer.parseInt(s.nextToken()); // 사이즈
            M = Integer.parseInt(s.nextToken()); // 벌통개수
            C = Integer.parseInt(s.nextToken()); //    용량
            map = new int[N][N];
            map_price = new int[N][N-M+1];

            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(s.nextToken());
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N-M+1; j++) {
                    DFS(i,j,0,0,0); //y좌표 , x좌표, 카운트, 용량, 이익
                    map_price[i][j] = max_subset; 
                    max_subset = 0;
                }
            }
//////////////////////////////////////DFS로 추출한 값 비교 ->제일 큰 조합 찾기////////////////////////////////////////////
            int max=0;
            for (int c = 0; c < N; c++) {
                for (int f = 0; f < N-M+1; f++) {
                    int select = map_price[c][f];
                    for (int i = c; i < N; i++) {
                        if(i == c)
                        {
                            for (int j = f+M; j < N-M+1; j++) 
                            {
                                if(max < select+map_price[i][j])
                                    max = select+map_price[i][j];
                            }
                        }
                        else
                        {
                            for (int j = 0; j < N-M+1; j++) 
                            {
                                if(max < select+map_price[i][j])
                                    max = select+map_price[i][j];
                            }
                        }
                    }
                }
            }


            System.out.println("#"+test_case+" "+max);
        }
    }
    private static void DFS(int y,int x,int cnt,int size, int price) {
        if(size > C)
            return;
        else if(cnt == M) //2칸 차지하면
        {
            if(max_subset < price) 
                max_subset = price;
            return;
        }

        DFS(y,x+1,cnt+1,size+map[y][x],price+map[y][x]*map[y][x]); // 부분집합중에 선택할 때
        DFS(y,x+1,cnt+1,size,price); //부분 집합중에 선택 안할 때
    }


}