SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
<풀이>
1. 한 지점에서 가로로 M만큼 꿀을 채취했을 때, 합은 C이하이면서 제곱의 합은 가장 큰 경우를 찾고, 그 때 제곱의 합을 다른 배열에 저장한다.(모든 지점에서 이 행위를 반복한다.)
2. (A양봉업자 최대이윤 + B양봉업자 최대이윤)의 최댓값을 구해서 출력한다.
<해법>
1. 한 지점에서 가로로 M만큼 꿀을 채취했을 때, 최대이윤을 구하는 방법
=> 문제를 간단하게 생각(합은 C이하, 제곱의 합이 가장 큰 경우 생각X)하면, 숫자들의 '조합'을 구하는 문제와 같습니다. 저는 재귀함수를 이용해서 먼저 조합을 구현하였고, 그 이후에 조건들을 덧붙여가며 문제를 해결했습니다.
(전체적인 문제를 해결한 흐름입니다.)
|
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
|
#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;
}
|
재귀함수와 구현에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글
| [C++] SWEA 2477 - 차량 정비소 (0) | 2022.11.30 |
|---|---|
| [C++] SWEA 5653 - 줄기세포배양 (0) | 2022.11.29 |
| [C++] SWEA 1486 - 장훈이의 높은 선반 (0) | 2021.01.21 |
| [C++] SWEA 1861 - 정사각형 방 (0) | 2021.01.21 |
| [C++] SWEA 4408 - 자기 방으로 돌아가기 (0) | 2021.01.17 |
