삼성 S/W expert 2115번 벌꿀 채취

2115번 벌꿀 채취

- N*N 크기의 map에 벌꿀의 양이 각각 들어가 있다. 2명의 사람이 벌꿀을 채취하는데 벌꿀을 가로 형태로만 채취할 수 있고 주어진 통의 갯수만큼만 채취 가능하다. 예를 들어 M=2 이면 {(0,0), (0,1)} 칸의 벌꿀을 채취할 수 있다. 채취한 벌꿀을 제곱하고 더해 Profit을 계산할 수 있다. 8, 9를 채취했다면 64+81 = 145 가 Profit이 된다. 여기서 최대로 채취할 수 있는 벌꿀의 양이 주어진다. 2명의 사람이 영역을 겹치지 않고 벌꿀을 채취했을 때 가장 큰 Profit을 구하는 문제다.

- 우선 2명의 사람이 겹치지 않게 영역을 나눴고, 최대 이익을 산출하기 위해 비트 마스킹으로 나올 수 있는 모든 이익을 계산했다.

#include <iostream>
#include <cmath>
using namespace std; 
int N, M, C;
int map[11][11];
int X=0, Y = 0;
int ans = 0;
 
void collectA(int x ,int y) {
    int totSumA = 0;
    int sumA;
    int honeysumA;
    for (int i = 1; i < (1 << M); i++) {
        honeysumA = 0;
        sumA = 0;
        for (int j = 0; j < M; j++) {
            if ((i & (1 << j)) > 0) {  if (honeysumA + map[x][y + j] <= C) { honeysumA += map[x][y + j];  sumA += map[x][y + j] * map[x][y + j]; } }
        }
        if (totSumA < sumA) { totSumA = sumA; }
    }
    X = totSumA;
}
 
void collectB(int x, int y) {
    int totSumB = 0;
    int honeysumB;
    int sumB = 0;
    for (int i = 1; i < (1 << M); i++) {
        honeysumB = 0;
        sumB = 0;
        for (int j = 0; j < M; j++) {
            if ((i& (1 << j)) > 0) { if (honeysumB + map[x][y + j] <= C) { honeysumB += map[x][y + j];  sumB += map[x][y + j] * map[x][y + j]; } }
        }
        if (totSumB < sumB) { totSumB = sumB; }
    }
    Y = totSumB;
}
bool c = true;
 
void solve() { 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N - M; j++) {
            collectA(i, j);
            for (int a = i; a < N; a++) {
                for (int b = 0; b <= N - M; b++) {
                    if (a == i) { if (b <= j) continue; }
                    c = true;
                    for (int t = 0; t < M; t++) { if (i == a && j + t == b) { c = false; break; } }
                    if(c){ collectB(a, b); }
                    if (ans < X + Y &&  X>0 && Y >0) { ans = X + Y; }
                    Y = 0;
                }
            }
            X = 0;
        }
    }
}
 
int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N >> M >> C;
        ans = 0;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                cin >> map[a][b];
            }
        }
        solve();
        cout <<"#"<< i<<' '<<  ans << endl;
    }
    return 0;
}