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

SWEA/삼성SW역량테스트 C++

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

IamToday 2020. 4. 28. 11:07

문제

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

불러오는 중입니다...

풀이

* 완전 탐색

* 각 row에서 m만큼 벌통들을 보면서 최대 C이하가 되는 최적의 조합을 구해야 한다.

* cost[][] 에는 현재 위치에서 m만큼 봤을 때 채취할 수 있는 벌꿀의 최대 수익을 저장한다.

* 전체 맵을 순회하면서 서로 겹치지 않는 두 지점의 최대 수익의 합을 구한다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n, m, c;
int map[11][11];
int cost[11][11];
bool chk[6];
int value = 0;
typedef pair<int, int> pp;

int max(const int &a, const int &b)
{
    if (a > b)
        return a;
    return b;
}
void calc(vector<int> &arr)
{
    int res = 0;
    for (int i = 0; i < arr.size(); i++)
    {
        if (chk[i])
        {
            res += arr[i] * arr[i];
        }
    }
    value = max(res, value);
}
void makeComb(int idx, int amount, vector<int> &arr)
{
    if (idx == arr.size())
    {
        //m개를 뽑았음
        return;
    }
    for (int i = idx; i < arr.size(); i++)
    {
        if (!chk[i])
        {
            if (amount + arr[i] > c)
                continue;
            chk[i] = true;
            calc(arr);
            makeComb(i + 1, amount + arr[i], arr);
            chk[i] = false;
        }
    }
}
int main()
{

ios_base::sync_with_stdio(0);
    cin.tie(0);

int t;
    cin >> t;

for (int tc = 1; tc <= t; tc++)
    {
        memset(cost, 0, sizeof(cost));

cin >> n >> m >> c;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
            }
        }

for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {

value = 0;
                if (m == 1)
                {
                    value = map[i][j] * map[i][j];
                }
                else
                {
                    //m개를 뽑는데, c를 넘지 않는 요소들을 뽑는다.
                    vector<int> arr;
                    memset(chk, 0, sizeof(chk));
                    for (int k = 0; k < m && j + k < n; k++)
                    {
                        arr.push_back(map[i][j + k]);
                    }
                    makeComb(0, 0, arr);
                }

cost[i][j] = value;
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int tmp = cost[i][j];
                int tmp2 = 0;
                if (j + m + m < n)
                {
                    int idx = j + m;
                    for (int k = idx; k < n; k++)
                    {
                        tmp2 = max(tmp2, cost[i][k]);
                    }
                }
                if (i != n - 1)
                {
                    for (int k = i + 1; k < n; k++)
                    {
                        for (int l = 0; l < n; l++)
                        {

tmp2 = max(tmp2, cost[k][l]);
                        }
                    }
                }
                if (ans < tmp + tmp2)
                {
                    // cout << tmp << " " << tmp2 << '\n';
                    ans = tmp + tmp2;
                }
            }
        }
       
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}