[SW Expert Academy] 2115. 벌꿀 채취

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define p pair<int,int>
using namespace std;

int map[10][10];
int ans;
int n,m,c;

int cal_dfs(vector<int> v, int idx, int origin_sum, int pow_sum){
    int tmp = -1;
    if(idx == v.size()){
        return pow_sum;
    }
    
    int _tmp;
    // Include
    if(origin_sum + v[idx] <= c){
        _tmp = cal_dfs(v,idx+1, origin_sum + v[idx], pow_sum + (v[idx] * v[idx]));
        tmp = tmp < _tmp ? _tmp : tmp;
    }
    
    // Pass
    _tmp = cal_dfs(v,idx+1, origin_sum, pow_sum );
    tmp = tmp < _tmp ? _tmp : tmp;
    
    return tmp;
}


int cal(int st_row, int st_col, int end_col){
    vector<int> v;
    for(int i=st_col; i<=end_col; i++){
        v.push_back(map[st_row][i]);
    }
    int ans = cal_dfs(v,0,0,0);
    return ans;
}

void dfs(int st_row, int st_col, int sum, int m_cnt){
    if(m_cnt == 2){
        ans = ans < sum ? sum : ans;
        return ;
    }
    
    for(int i=st_row; i<n; i++){
        int continue_cnt = 0;
        for(int j=st_col; j<n; j++){
            continue_cnt ++;
            if(continue_cnt == m){
                continue_cnt = 0;
                /*
                 n = 5
                 m = 3
                 row index = 1 이라고 가정하면
                 [ 1,0 -> 1,2 | 1,1 -> 1,3 | 1,2 -> 1,4 | 1,3 -> 1,5 ]
                 이렇게 체크를 해야한다.
                 그런데 지금 로직이라면 j=0에서 2가 됐을 때
                 그 다음 체크하는 위치는 j=3이 된다.
                 그런데 j=0일 때 체크하고 다음은 j=1일 때 체크해야한다.
                 그렇기 때문에 j-m+1(= 2-3+1)하게 되면 j는 0이 되고
                 for(;;j++) 조건에 의해서 j=1이 되고
                 j=1일 때 체크가 가능해진다.
                 */
                int tmp_sum = cal(i, j-m+1 ,j);
                dfs(i,j+1,sum + tmp_sum, m_cnt + 1);
                j = j-m+1;
            }
        }
        st_col = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = -1;
        
        cin >> n >> m >> c;
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> map[i][j];
        
        dfs(0,0,0,0);
        
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int n,m,c;
int map[10][10];
int dp[10][10];

int cal(vector<int> &v, int idx, int sum, int profit){
    if(sum > c) return 0;
    if(idx == v.size()) return profit;
    
    // 해당 idx 벌꿀을 채취했을 경우 O
    int res_1 = cal(v,idx+1, sum + v[idx], profit + (v[idx] * v[idx]));
    
    // 해당 idx 벌꿀을 채취했을 경우 X
    int res_2 = cal(v,idx+1, sum, profit);
    
    return max(res_1, res_2);
}

int getMaxCost(int x,int y){
    vector<int> v;
    for(int i=0; i<m; i++)
        v.push_back(map[x][y+i]);
    return cal(v, 0, 0, 0 );
}

int dfs(int x, int y){
    int ans = -1;
    // 같은 Line
    for(int i=y; i<n-m+1; i++)
        ans = max(ans, dp[x][i]);
    
    // 다음 Line
    for(int i=x+1; i<n; i++)
        for(int j=0; j<n-m+1; j++)
            ans = max(ans, dp[i][j]);
    
    return ans;
}

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        memset(map,0,sizeof(map));
        memset(dp,0,sizeof(dp));
        cin >> n >> m >> c;
        
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        /*
         i,j부터 m까지 MaxCost 구하기
         i = 2 | j = 3 | m = 5 일경우
         dp[2][3] = map[2][3] ~ map[2][8] 사이의 최대 값을 구해놓는다.
         */
        for(int i=0; i<n;i ++)
            for(int j=0; j<n-m+1; j++)
                dp[i][j] = getMaxCost(i, j);
        
        int res = -1;
        for(int i=0; i<n;i ++)
            for(int j=0; j<n-m+1; j++)
                res = max(res, dfs(i,j+m) + dp[i][j] );
        
        printf("#%d %d\n",tc, res);
    } // end of for tc
    return 0;
}

//벌꿀채취 이준용
#include <cstdio>
#include <cstring>
using namespace std;
int T, N, M, C, AnsB, Ans, map[10][10];
void Input() {
    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]);
    Ans = 0;
}

int Abs(int a) { return a > 0 ? a : -a; }

void PersonB(int x, int y) {
    AnsB = 0;
    for (int a = x; a < N; a++)
        for (int b = 0; b <= N - M; b++) {
            if (a == x && Abs(y - b) < M) continue;
        
            for (int i = 1; i < (1 << M); i++) {
                int SumB = 0, CheckB = 0;
                
                for (int j = 0; j < M; j++)
                    if (i & (1 << j)) {
                        CheckB += map[a][b + j];
                        SumB += map[a][b + j] * map[a][b + j];
                    }
                
                if (CheckB <= C && AnsB < SumB)
                    AnsB = SumB;
            }
        }
}

void PersonA(int x, int y) {
    for (int i = 1; i < (1 << M); i++) { // 2n-1번 Loop
        int SumA = 0, CheckA = 0;
        
        for (int j = 0; j < M; j++)
            if (i & (1 << j)) {
                CheckA += map[x][y + j];
                SumA += map[x][y + j] * map[x][y + j];
            }
        
        if (CheckA <= C) {
            PersonB(x, y);
            if (Ans < AnsB + SumA)
                Ans = AnsB + SumA;
        }
    }
}

void CheckMap() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= N - M; j++)
        PersonA(i, j);
}

int main() {
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        Input();
        CheckMap();
        printf("#%d %d\n", tc, Ans);
    }
}