[SWEA][모의 SW 역량테스트][C++] 2115 벌꿀채취

문제

SWEA 모의 SW 역량테스트 - 2115 벌꿀채취

SW Expert Academy

 

---

문제 풀이

접근 방식

각 칸에서부터 가로로 M개의 칸의 벌통들을 선택하였을 때,

그 칸들에서 나올 수 있는 모든 조합을 확인하여 최댓값을 구하였고,

각 줄마다 그 결괏값들의 최댓값을 구해서 가장 큰 값 2개를 더하여 최대 수익을 구하였다.

(예제의 설명과 달리, 각 줄에서 최대 1개만 선택해야 모든 테스트 케이스를 통과할 수 있음)

 

hive 벡터에는 주어진 벌통들의 값을 저장하였고,

제곱값이 문제를 풀 때 계속 필요해서 square 벡터에 hive의 제곱값을 저장하였다.

result 벡터에는 해당 칸에서부터 M개의 칸의 벌통들의 조합에서 나올 수 있는 최대 수익을 저장하였다.

 

1. result 벡터 채우기

 - hive[i][j]에서 hive[i][j+M - 1]까지의 합 ≤ C이면, result[i][j]는 제곱값들의 합

 - hive[i][j]에서 hive[i][j+M - 1]까지의 합 > C이면,

   result[i][j]는 벌통 M개 중에서 1개, 2개, ..., M-1개를 선택했을 때의 최댓값 : DFS로 구현

void dfs(int i, int j, int m, int count) {
    int len = choose.size();
    if (len == count) {
        int sum1 = 0;
        int sum2 = 0;
        for (int a = 0; a < len; a++) {
            sum1 += hive[i][choose[a]];
            sum2 += square[i][choose[a]];
        }
        if (sum1 <= C) {
            if (MAX < sum2)
                MAX = sum2;
        }
        return;
    }
 
    for (int a = j; a < m; a++)  {
        choose.push_back(a);
        dfs(i, a + 1, m, count);
        choose.pop_back();
    }
}

2. 최대 수익 구하기

 - 위의 과정을 수행하며 각 행마다의 최댓값을 best 벡터에 넣어주었다.

 - best를 정렬하여 상위 2개의 값을 더해 최대 수익을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M, C, MAX;
 
vector<vector<int>> hive;
vector<vector<int>> square;
vector<vector<int>> result;
vector<int> choose;
 
void dfs(int i, int j, int m, int count) {
    int len = choose.size();
    if (len == count) {
        int sum1 = 0;
        int sum2 = 0;
        for (int a = 0; a < len; a++) {
            sum1 += hive[i][choose[a]];
            sum2 += square[i][choose[a]];
        }
        if (sum1 <= C) {
            if (MAX < sum2)
                MAX = sum2;
        }
        return;
    }
 
    for (int a = j; a < m; a++)  {
        choose.push_back(a);
        dfs(i, a + 1, m, count);
        choose.pop_back();
    }
}
 
int main(int argc, char** argv) {
    int test_case;
    int T, i, j, k, sum, answer;
    // freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기
        cin >> N >> M >> C;
        hive.assign(N, vector<int>(N));
        square.assign(N, vector<int>(N));
        result.assign(N, vector<int>(N - M + 1));
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++)  {
                cin >> hive[i][j];
                square[i][j] = hive[i][j] * hive[i][j];
            }
        }
 
        // 벌통 선택 시의 결과값 구하기
        vector<int> best;
        for (i = 0; i < N; i++) {
            for (j = 0; j < N - M + 1; j++) {
                sum = 0;
                for (k = 0; k < M; k++)  {
                    sum += hive[i][j + k];
                    result[i][j] += square[i][j + k];
                }
                if (sum > C) {
                    MAX = 0;
                    choose.clear();
                    for (k = 1; k < M; k++)  {
                        dfs(i, j, j + M, k);
                    }
                    result[i][j] = MAX;
                }
            }
            best.push_back(*max_element(result[i].begin(), result[i].end()));
        }
 
        // 최대 수익 구하기
        sort(best.begin(), best.end());
        answer = best[N-1];
        answer += best[N-2];
        cout << "#" << test_case << " " << answer << "\n";
    }
    return 0;
}

실행 결과