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

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

 

 

 

 알고리즘 

 

각 칸마다 구할 수있는 최대값 을 구한뒤 제약사항을 주의 하며 합새거 가장 높은 경우를 출력.

 

 코드 

colorscripter.com/info#e"

 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
 
int N, M, C;
 
int map[11][11];
int ans1 = 0, ans2 = 0;
 
int arr[5];
bool sel[5];
int max_num = 0;
 
int square() {
 
    int sum = 0;
    for (int i = 0; i < M; i++) {
        if (sel[i] == true) {
            sum = sum + arr[i] * arr[i];
        }
    }
    return sum;
}
 
 
int Sum() {
 
    int sum = 0;
    for (int i = 0; i < M; i++) {
        if (sel[i] == true) {
            sum += arr[i];
        }
    }
    return sum;
}
 
//벌통 선택
void pick(int y, int x) {
    int idx = 0;
    for (int i = x; i < x + M; i++) {
        arr[idx++] = map[y][i];
    }
}
 
void DFS(int idx, int cnt) {
    
    
    //벌통의 갯수보다 많이탐색할수 없다 .
    if (cnt > M)return;
 
    //최대 수확량보다 많으면 return
    if (cnt > 0) {
        if (Sum() > C)return;
 
 
        //최댓값 갱신
        max_num = max(max_num, square());
    }
    for (int i = idx; i < M; i++) {
        if (sel[i] == true) continue;
        sel[i] = true;
        DFS(i, cnt + 1);
        sel[i] = false;
 
    }
}
void reset() {
    for (int i = 0; i < 5; i++) {
        sel[i] = false;
        arr[i] = 0;
    }
}
 
void func() {
    int y = 0;
    int x = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N-M; j++) {
            pick(i, j);
            DFS(0, 0);
            if (max_num > ans1) {
                ans1 = max_num;
                y = i;
                x = j;
            }
 
        }
    }
    reset();
    max_num = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N - M; j++) {
            if (y == i && j == x) {
                j += M;
                continue;
            }
            pick(i, j);
            DFS(0, 0);
            ans2 = max(max_num, ans2);
        }
    }
    reset();
    max_num = 0;
}
 
int main() {
    int T;
    cin >> T;
    for (int k = 1; k <= T; k++) {
        cin >> N >> M >> C;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        func();
        cout << "#" << k << " " << ans1 + ans2 << "\n";
        ans1 = 0;
        ans2 = 0;
    }
 
}
 

 

개인적으로 SW EXPERT 문제는 설명이 부족한부분이 많아서 별로인거같다 기출이기 때문에 풀어보는것..