SW Expert Academy - 2115. 벌꿀채취
문제링크
문제설명
- N x N 개의 벌통이 정사각형 모양으로 배치되어 있다.
- 각 칸의 숫자는 각각의 벌통에 있는 꿀의 양을 나타내며, 꿀의 양은 서로 다를 수 있다.
- 벌꿀을 채취하는 과정은 다음과 같다.
- 두 명의 일꾼이 있다. 꿀을 채취할 수 있는 벌통의 수 M이 주어질 때, 각각의 일꾼은 가로로 연속되도로기 M개의 벌통을 선택하고, 선택한 벌통에서 꿀을 채취할 수 있다. 단, 두명의 일꾼이 선택한 벌통은 서로 겹치면 안된다.
- 두 명의 일꾼은 선택한 벌통에서 꿀을 채취하여 용기에 담아야 한다. 단, 서로 다른 벌통에서 채취한 꿀이 섞이게 되면 상품가치가 떨이지게 되므로, 하나의 벌통에서 채취한 꿀은 하나의 용기에 담아야 한다. 하나의 벌통에서 꿀을 채취할 때, 일부분만 채취할 수 없고 벌통에 있는 모든 꿀을 한번에 채취해야 한다. 두 일꾼이 채취할 수 있는 꿀의 최대 양은 C 이다.
- 예를 들어, C가 10인데 꿀의 양이 8과 5인 두 개의 벌통에서 모두 꿀을 채취하는 경우 채취한 꿀의 양이 13이 되므로 둘 중 하나의 벌통에서만 꿀을 채취해야 한다.
- 채취한 꿀은 시장에서 팔리게 된다. 이때 하나의 용기에 있는 꿀의 양이 많을수록 상품가치가 높아, 각 용기에 있는 꿀의 양의 제곱만큼의 수익이 생긴다.
- 채취한 벌통의 꿀의 양이 6, 1, 8 세가지 인 경우 수익의 합은 (6 x 6) + (1 x 1) + (8 x 8) = 101이 된다.
- 두 일꾼이 꿀을 채취하여 얻을 수 있는 최대 수익을 구하라
문제접근1
- 완전탐색 으로 채취 가능한 모든 벌통 조합의 경우의 수를 찾고, 각 경우의 수마다 채취할 수 있는 꿀의 양이 최대가 되는 경우를 비교해가며 최대 수익을 찾는 방법으로 문제를 해결했다.
- 일꾼들은 각 행마다 M개의 연속된 벌통을 고를 수 있는데, 일꾼1 이 선택한 벌통 조합을 기준으로 일꾼2가 겹치지 않고 선택가능한 벌통 조합을 찾아 해당 조합의 최대 수익을 계산할 수 있도록 했다.
- 일꾼2가 일꾼1과 같은 행에서 벌통을 선택하는 경우 일꾼1이 선택한 마지막 벌통 이후에 선택할 수 있는 충분한 벌통이 있는 경우에만 벌통을 선택할 수 있도록 했다.
- 일꾼1이 선택한 벌통 앞쪽을 고려하지 않은 이유는 이전에 일꾼1이 선택한 조합에 대해 일꾼2가 선택한 조합과 중복되기 때문이다.
- 일꾼2가 일꾼1과 다른 행에서 벌통을 선택하는 경우 선택 가능한 모든 경우의 수를 찾아 벌통을 선택한다.
- 선택한 벌통들을 꿀의 양을 기준으로 내림차순 정렬한 후 꿀의 양의 합이 C를 넘지 않는 경우를 찾아 최대 이익을 계산한다.
구현1
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_N 10
using namespace std;
int N, M, C;
int honeyMap[MAX_N][MAX_N];
int getProfit(vector<int>& worker)
{
int ret = 0;
// 벌통에 들어있는 꿀의 양을 기준으로 내림차순 정렬
sort(worker.begin(), worker.end(), greater<int>());
// 수집 가능한 모든 경우에 대해 이익을 계산하고, 최대 값을 찾는다.
for (int i = 0; i < worker.size(); i++)
{
vector<int> cand;
int curHoney = worker[i];
if (curHoney <= C) cand.push_back(worker[i]);
int j = i + 1;
while (true)
{
if (j == worker.size()) break;
if (curHoney + worker[j] <= C)
{
cand.push_back(worker[j]);
curHoney += worker[j];
}
j++;
}
int profit = 0;
for (auto ele : cand)
{
profit += (ele * ele);
}
ret = max(ret, profit);
}
return ret;
}
// 다른 한명의 일꾼이 채집가능한 M개의 벌통을 선택하고, 최종 이익을 계산한다.
int selectOtherWorker(int startX, int startY, vector<int>& worker2, int profitWorker1)
{
worker2.clear();
for (int i = 0; i < M; i++)
{
worker2.push_back(honeyMap[startX][startY + i]);
}
int profitWorker2 = getProfit(worker2);
return profitWorker1 + profitWorker2;
}
int solution()
{
int ret = 0;
// 일꾼 한명이 먼저 채집할 M개의 벌통을 선택한다.
for (int r = 0; r < N; r++)
{
for (int c = 0; c <= N - M; c++)
{
vector<int> worker1, worker2;
for (int i = 0; i < M; i++)
{
worker1.push_back(honeyMap[r][c + i]);
}
int end = c + M; //
int rear = N - (c + end); // 뒷칸 개수
int profitWorker1 = getProfit(worker1); // 일꾼 1의 최대 이익
// 나머지 일꾼의 벌통을 선택하고, 이익을 계산한다.
for (int sr = r; sr < N; sr++)
{
// 나머지 한명의 일꾼이 채집 가능한 M개의 벌통을 선택한다.
// 같은 행인 경우 겹치지 않고 선택 가능한지 확인한다.
if (r == sr)
{
if (rear >= M)
{
for (int sy = end; sy <= end + rear - M; sy++)
{
ret = max(ret, selectOtherWorker(sr, sy, worker2, profitWorker1));
}
}
}
else // 다른 행에서 선택하는 경우
{
for (int sy = 0; sy <= N - M; sy++)
{
ret = max(ret, selectOtherWorker(sr, sy, worker2, profitWorker1));
}
}
}
}
}
return ret;
}
int main(int argc, char** argv)
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int test_case;
int T;
// freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N >> M >> C;
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
cin >> honeyMap[r][c];
}
}
int ans = solution();
cout << "#" << test_case << " " << ans << "\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
문제접근2
- 일꾼1, 일꾼2 구분 없이 채취 가능한 벌꿀의 양을 모두 구한다.
- 벌통 시작 좌표와 해당 구간의 채취 가능한 최대 벌꿀 양을 데이터로
list벡터 컨테이너에 담는다.
- 벌통 시작 좌표와 해당 구간의 채취 가능한 최대 벌꿀 양을 데이터로
list벡터 컨테이너에서 쌍을 만든다. (벌통이 겹치는 경우 0을 반환하여 최솟값이 되도록 한다.)
구현2
#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#define MAX_N 10
#define MAX_VISIT 100
#define MAX_WORKER 2
#define NOT_VALID 0
using namespace std;
typedef struct data_t
{
int startX;
int startY;
int value;
} DATA;
int N, M, C;
int board[MAX_N][MAX_N];
vector<DATA> list;
vector<int> cand;
vector<int> tmp;
bool visited[MAX_VISIT];
void init()
{
list.clear();
}
void input()
{
init();
cin >> N >> M >> C;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
cin >> board[r][c];
}
}
}
int calculateHoneyValue(int v, int value, int curAmount)
{
if (curAmount > C) {
return value - cand[v -1 ] * cand[v - 1];
}
if (v >= M) return value;
int ret = 0;
for (int i = v; i < cand.size(); i++) {
if (visited[i]) continue;
visited[i] = true;
ret = max(ret, calculateHoneyValue(i + 1, value + cand[i] * cand[i], curAmount + cand[i]));
visited[i] = false;
}
return ret;
}
int getMaxHoney(int sx, int sy)
{
if (sy + M - 1 >= N) return 0;
cand.clear();
memset(visited, false, sizeof(visited));
for (int i = 0; i < M; i++) {
cand.push_back(board[sx][sy + i]);
}
return calculateHoneyValue(0, 0, 0);
}
bool cmp(DATA d1, DATA d2)
{
return d1.value > d2.value;
}
void collectHoney()
{
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int honeyVal = getMaxHoney(r, c);
if (honeyVal == 0) continue;
list.push_back({ r, c, honeyVal });
}
}
sort(list.begin(), list.end(), cmp);
}
int getProfit()
{
int worker1 = tmp[0];
int worker2 = tmp[1];
int lowBound = min(list[worker1].startY, list[worker2].startY);
int bigBound = max(list[worker1].startY + M - 1, list[worker2].startY + M - 1);
if (list[worker1].startX != list[worker2].startX) return list[worker1].value + list[worker2].value;
else if (bigBound - lowBound + 1 == 2 * M) return list[worker1].value + list[worker2].value;
return NOT_VALID;
}
int getMaxProfit(int v)
{
if (tmp.size() == MAX_WORKER) {
int profit = getProfit();
return profit;
}
int ret = 0;
for (int i = v; i < list.size(); i++) {
if (visited[i]) continue;
visited[i] = true;
tmp.push_back(i);
ret = max(ret, getMaxProfit(i + 1));
tmp.pop_back();
visited[i] = false;
}
return ret;
}
void test()
{
input();
collectHoney();
memset(visited, false, sizeof(visited));
tmp.clear();
cout << getMaxProfit(0) << endl;
}
int solution()
{
collectHoney();
memset(visited, false, sizeof(visited));
tmp.clear();
return getMaxProfit(0);
}
int main(int argc, char** argv)
{
int test_case;
int T = 0;
// freopen("input.txt", "r", stdin);
cin >> T;
// test();
for (test_case = 1; test_case <= T; ++test_case)
{
input();
cout << "#" << test_case << " " << solution() << endl;
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
Leave a comment