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

문제

 

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

불러오는 중입니다...

풀이

* 완전 탐색 

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

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

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

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

#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; }