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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

꿀을 선택하는게 아주 조금 까다로웠던 문제

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

ㅇㅏㅈㅏ 🤗