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

문제

 

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