[C++] SWEA 2115 - 벌꿀채취

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

SW Expert Academy

<풀이>

1. 한 지점에서 가로로 M만큼 꿀을 채취했을 때, 합은 C이하이면서 제곱의 합은 가장 큰 경우를 찾고, 그 때 제곱의 합을 다른 배열에 저장한다.(모든 지점에서 이 행위를 반복한다.)

2. (A양봉업자 최대이윤 + B양봉업자 최대이윤)의 최댓값을 구해서 출력한다.

 

<해법>

1. 한 지점에서 가로로 M만큼 꿀을 채취했을 때, 최대이윤을 구하는 방법

=> 문제를 간단하게 생각(합은 C이하, 제곱의 합이 가장 큰 경우 생각X)하면, 숫자들의 '조합'을 구하는 문제와 같습니다. 저는 재귀함수를 이용해서 먼저 조합을 구현하였고, 그 이후에 조건들을 덧붙여가며 문제를 해결했습니다.

 

(전체적인 문제를 해결한 흐름입니다.)

 

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M, C;
int honeyMap[10][10];       //주어진 입력 맵
int maxProfitMap[10][10];   //최대 이윤 맵
 
//벡터 v의 원소들로 조합하여, 합은 C보다 작으면서 가장 큰 이윤을 찾는 함수
int findMaxProfit(vector<int> v, int idx, int sum, int profit) {
 
    if (sum > C) {
        return 0;
    }
 
    int maxProfit = 0;
    maxProfit = max(maxProfit, profit);
 
    if (idx >= M) {
        return maxProfit;
    }
 
    for (int i = idx; i < M; i++) {
        maxProfit = max(maxProfit, findMaxProfit(v, i + 1, sum + v[i], profit + (v[i] * v[i])));
    }
    
    return maxProfit;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0, C = 0;
        memset(honeyMap, 0, sizeof(honeyMap));
        memset(maxProfitMap, 0, sizeof(maxProfitMap));
        int answer = 0;
 
        //입력
        cin >> N >> M >> C;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> honeyMap[i][j];
            }
        }
 
        /* 해법 */
        //1. 각 지점에서 가로로 M만큼 꿀을 채취했을 때, 가장 많은 이윤을 찾아 저장
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N - M; j++) {
                vector<int> v;
                for (int k = 0; k < M; k++) {
                    v.push_back(honeyMap[i][j + k]);
                }
                maxProfitMap[i][j] = findMaxProfit(v, 0, 0, 0);
            }
        }
 
        //2. (A양봉업자 최대이윤 + B양봉업자 최대이윤) 최댓값 구하기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N - M; j++) {
                int maxProfitSum = maxProfitMap[i][j];
 
                int maxProfit = 0;
                for (int k = i; k < N; k++) {
                    int startL = 0;
                    if (k == i) {
                        startL = j + M;
                    }
                    for (int l = startL; l <= N - M; l++) {
                        maxProfit = max(maxProfit, maxProfitMap[k][l]);
                    }
                }
 
                maxProfitSum += maxProfit;
                answer = max(answer, maxProfitSum);
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

재귀함수와 구현에 대해 알아볼 수 있는 문제였습니다.