2115 벌꿀채취

SWEA::2115 벌꿀채취

겹치지 않도록 m개 고르는 경우에 대해 백트래킹

비용계산에 대해 백트래킹 을 해야하는 문제이다.

겹치지 않도록 m개 고르는 방법에 있어서 굉장히 많은 고생을 했고,

두가지 방법으로 풀어보았다.

첫 번째 방법 : 먼저 m개를 고르고 그 이후에 나올 수 있는 모든 조합에 대해 골라 최대값 찾기

두 번째 방법 : 각각 벌통에 대해 올 수 있는 최댓값을 저장시킨 후 m개 씩 2개 골라 최대값 찾기

두 번째 방법이 훨씬 연산이 적어진다.

이유:

첫번째 방법으로 1 2 3 4 5 에서 2개를 고른다고 할때

1 2//1 3//1 4//1 5//2 3//2 4//2 5// ... // 4 5 ---> 이런식으로 중복되어 비용을 계산해야 하는 부분이 생긴다. 그러나 두번째 방법을 이용하면 중복되어 계산하는 부분이 없어지게 되므로 더 빠르게 문제해결이 가능하다.

<첫번째 방법>

#include <stdio.h>
#include <memory.h>
 
int map[10][10];
bool visited[10][10];
int n, m, c, res;
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
//비용 구하기
void getPrice(int x, int y, int a, int sum, int price) {
    if (sum > c) return ;
    res = max(res, price);
    if (a == m) return;
 
    getPrice(x, y + 1, a + 1, sum + map[x][y], price + map[x][y] * map[x][y]);
    getPrice(x, y + 1, a + 1, sum, price);
}
 
int solve(int x, int y) {
    //먼저 고른 m개의 벌통에 대해 비용 구하기
    for (int i = 0; i < m; i++) {
        visited[x][y + i] = true;
    }
    res = 0;
    getPrice(x, y, 0, 0, 0);
    int priceA = res;
 
    //나중에 고른 m개의 벌통에 대해 비용 구하며 비교하기
    int priceB = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-m+1; j++) {
            if (!visited[i][j]) {
                res = 0;
                getPrice(i, j, 0, 0, 0);
                priceB = max(priceB, res);
            }
        }
    }
 
    return priceA + priceB;
}
 
void init() {
    memset(visited, 0, sizeof(visited));
}
 
int main() {
    int t;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        init();
        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]);
            }
        }
 
        int mm = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-m+1; j++) {
                mm = max(mm, solve(i, j));
            }
        }
        printf("#%d %d\n", tc, mm);
    }
}

<두번째 방법>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int t, n, m, c;
int map[10][10];
int d[10][10];
 
//최대값 계산하기
int calc(vector<int> &v, int n, int sum, int val) {
    if (sum > c) return 0;
    if (n == v.size()) return val;
    
    return max(calc(v, n + 1, sum + v[n], val + v[n] * v[n]), calc(v, n + 1, sum, val));
}
 
// 최대값 찾기
int getMaxPrice(int x,int y) {
    vector<int> v;
    for (int i = 0; i < m; i++) {
        v.push_back(map[x][y + i]);
    }
    return calc(v, 0, 0, 0);
}
 
int dfs(int x,int y) {
    int ans = 0;
    //같은라인
    for (int i = y + m; i < n - m + 1; i++) {
        ans = max(ans, d[x][i]);
    }
    //다음라인
    for (int i = x + 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, d[i][j]);
        }
    }
    return ans;
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        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]);
                d[i][j] = 0;
            }
        }
 
        //d배열에 그칸부터 m칸까지의 최대값 저장
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - m + 1; j++) {
                d[i][j] = getMaxPrice(i, j);
            }
        }
 
        //i,j를 선택한 상태에서 찾을수 있는 나머지에 대해
        //비교하여 최대값 찾는다.
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - m + 1; j++) {
                res = max(res, dfs(i, j)+d[i][j]);
            }
        }
        printf("#%d %d\n", tc, res);
    }
}