Problem Solving/SWEA
SWEA 2115번: [모의 SW 역량테스트] 벌꿀채취
이진2
2020. 5. 26. 21:59
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
꿀을 선택하는게 아주 조금 까다로웠던 문제
A와 B 둘다 각각 연속된 M개의 좌표를 선택한 뒤 각각 그 중에서 얻을 수 있는 최대 꿀의 양을 구해 수익을 계산하는 방법이다
이렇게 맵에서 특정 좌표를 여러 개 구하는 문제는 시간초과가 나지 않게 해주는 것이 핵심이다
예를 들면, 한 좌표를 골랐을 때 다음 경우는 그 이후의 좌표부터 구해주는 것이다
나는 A 영역이 무조건 B 영역보다 앞에 오게끔 경우를 나누어줬다
그러면 좌표를 구하는 경우의 수가 최대 O(N^N)에서 O(N!)으로 줄어든다
위처럼 수도코드를 정리하고 코드로 짠다(수도코드를 잘 짜는 경우는 문제푸는데 20~30분밖에 안 걸릴 수도 있당 😎)
처음에는 꿀의 양이 C 이내가 될 때까지 양이 적은 순으로 하나씩 빼주면 될 줄 알았는데 꼭 그런건 아니었다
(ex. C가 10일 때 5 5 7)
그래서 해당 영역 내에서 얻을 수 있는 최대 꿀의 경우의 수를 구해주는 코드로 수정했다
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, c,tc,map[11][11],ans,money[2];
vector<int> v[2];
bool desc(int a, int b) { return a > b; }
int maxmoney(int num,int sum,int p,int dep) {
if (sum > c)return -1;
if (dep == v[num].size()) {
if (p > money[num])money[num] = p;
return sum;
}
int a = maxmoney(num, sum,p, dep + 1);
int b = maxmoney(num, sum + v[num][dep], p + v[num][dep]*v[num][dep], dep + 1);
return a > b ? a : b;
}
void honey(int s,int d,int num) {
for (int i = d; i < n; i++) {
//if(num==1)
for (int j = 0; j < n; j++) {
if (num == 1 && i == d&&!j)j = s;
if (j + m - 1 >= n)break; //범위 넘어가면 다음 줄
int sum = 0;
for (int k = j; k < j + m; k++) {
v[num].push_back(map[i][k]);
sum += map[i][k];
}
maxmoney(num, 0, 0, 0);
if (num) { //2번째까지 다 왔담연
int a = money[0]+money[1];
//for (int k = 0; k < 2; k++)
// for (auto x : v[k])
// a += x * x;
if (a > ans)
ans = a;
}
else {
honey(j + m, i, 1);
}
v[num].clear();
money[num] = 0;
}
}
}
int main() {
scanf("%d", &tc);
for (int T = 1; T <= tc; T++) {
ans = 0;
scanf("%d%d%d", &n, &m, &c);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &map[i][j]);
for (int i = 0; i < n; i++)
for (int j = m; j < n; j++);
honey(0, 0,0);
printf("#%d %d\n", T,ans);
money[0]=money[1] = 0;
}
return 0;
}
ㅇㅏㅈㅏ 🤗