SW Expert Academy 2115. 벌꿀채취

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

걸린 시간

02 : 01 : 39

문제

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define INF 987654321
using namespace std;

int n, m, c;

int put(int sy, int sx, vector<vector<int>>& honey){
    int ret = 0;
    // mC1
    for(int i = sx; i < sx+m; i++)
        if(honey[sy][i] <= c)
            ret = max(ret, honey[sy][i]*honey[sy][i]);
    // mC2
    if(m < 2) return ret; 
    for(int i = sx; i < sx+m-1; i++)
        for(int j = i+1; j < sx+m; j++)
            if(honey[sy][i] + honey[sy][j] <= c)
                ret = max(ret, honey[sy][i]*honey[sy][i] + honey[sy][j]*honey[sy][j]);
    // mC3
    if(m < 3) return ret; 
    for(int i = sx; i < sx+m-2; i++)
        for(int j = i+1; j < sx+m-1; j++)
            for(int k = j+1; k < sx+m; k++)
                if(honey[sy][i] + honey[sy][j] + honey[sy][k] <= c)
                    ret = max(ret, honey[sy][i]*honey[sy][i] + honey[sy][j]*honey[sy][j] + honey[sy][k]*honey[sy][k]);
    // mC4
    if(m < 4) return ret;
    for(int i = sx; i < sx+m-3; i++)
        for(int j = i+1; j < sx+m-2; j++)
            for(int k = j+1; k < sx+m-1; k++)
                for(int l = k+1; l < sx+m; l++)
                    if(honey[sy][i] + honey[sy][j] + honey[sy][k] + honey[sy][l] <= c)
                        ret = max(ret, honey[sy][i]*honey[sy][i] + honey[sy][j]*honey[sy][j] + honey[sy][k]*honey[sy][k] + honey[sy][l]*honey[sy][l]);
    // mC5
    if(m < 5) return ret; 
    if(honey[sy][sx] + honey[sy][sx+1] + honey[sy][sx+2] + honey[sy][sx+3] + honey[sy][sx+4] <= c)
        ret = max(ret, honey[sy][sx]*honey[sy][sx] + honey[sy][sx+1]*honey[sy][sx+1] + honey[sy][sx+2]*honey[sy][sx+2] + honey[sy][sx+3]*honey[sy][sx+3] + honey[sy][sx+4]*honey[sy][sx+4]);
    return ret;
}

int two(int sy, int sx, vector<vector<int>>& honey){
    int ret = 0;
    // 같은 줄
    for(int x = sx; x < n-m+1; x++){
        int tmp = 0;
        tmp += put(sy, x, honey);
        ret = max(ret, tmp);
    }
    // 다음 줄
    for(int y = sy+1; y < n; y++){
        for(int x = 0; x < n-m+1; x++){
            int tmp = 0;
            tmp += put(y, x, honey);
            ret = max(ret, tmp);
        }
    }
    return ret;    
}

int one(vector<vector<int>>& honey){
    int ret = 0;
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n-m+1; x++){
            int tmp = 0;
            tmp += put(y, x, honey);
            tmp += two(y, x+m, honey);
            ret = max(ret, tmp);
        }
    }
    return ret;
}

int main()
{
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> n >> m >> c;
        vector<vector<int>> honey(n, vector<int>(n));
        for(int y = 0; y < n; y++)
            for(int x = 0; x < n; x++)
                cin >> honey[y][x];
        cout << "#" << test_case << " " << one(honey) << "\n";
    }
    return 0;
}

수익이 최대가 되도록 꿀을 채취하는 함수의 구현이 관건이였는데, 효율적인 알고리즘이 생각이 나질 않아 m개의 벌통에서 1개부터 m개를 고르는 경우의 수를 모두 중첩 for 문으로 일일이 구해주었다. m이 최대 5로 크지 않은 수였기 때문에 가능했던 풀이.