SWEA 2115번: 벌꿀채취

문제

문제 바로가기> SWEA 2115번: 벌꿀채취

SW Expert Academy

 

풀이

1. 부분집합을 이용하여, 해당 지점(y, x) 에서 얻을 수 있는 가장 큰 수익을 profit[y][x]에 저장한다.

2. 조합을 이용하여, 일꾼 두명이 얻을 수 있는 최대 수익을 구한다.

 

JAVA

import java.io.*;
import java.util.*;
 
public class Solution {
     
    static BufferedReader br = null;
     
    static int N, M, C, ans;
    static int[][] map, profit;
     
    static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        profit = new int[N][N];
         
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
     
    static void get_profit(int y, int x, int cnt, int honey, int revenue) {
        if(honey > C) return;
        if(cnt == M) {
            profit[y][x-M] = Math.max(profit[y][x-M], revenue);
            return;
        }
        get_profit(y, x+1, cnt+1, honey+map[y][x], revenue+(map[y][x]*map[y][x])); // 채취 
        get_profit(y, x+1, cnt+1, honey, revenue); // 미채취 
    }
     
    static void make_profit() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<=N-M; j++) get_profit(i,j,0,0,0);
        }
    }
 
    static void collect_honey(int y, int x, int cnt, int revenue) {
        if(cnt==2) {
            ans = Math.max(ans, revenue);
            return;
        }
        for(int i=y; i<N; i++) {
            for(int j=x; j<=N-M; j++) collect_honey(i, j+M, cnt+1, revenue+profit[i][j]);
            x=0; // for the next row
        }
    }
     
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++){
            ans=0;
            input();
            make_profit();
            collect_honey(0,0,0,0);
            sb.append("#"+t+" "+ans+"\n");
        }
        System.out.println(sb.toString());
    }
}

 

C++

#include <iostream>
#define MAX 11
using namespace std;

int ans;
int N, M, C;
int maxProfit[2];
int map[MAX][MAX];

void input(){
    cin >> N >> M >> C;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++) cin >> map[i][j];
    }
}

void get_max_profit(int y, int x, int num, int cnt, int honey, int profit){
    if(honey > C) return;
    if(cnt == M){
        maxProfit[num] = max(profit, maxProfit[num]);
        return;
    }
    get_max_profit(y, x + 1, num, cnt + 1, honey, profit); // 미채취
    get_max_profit(y, x + 1, num, cnt + 1, honey+map[y][x], profit+map[y][x]*map[y][x]); // 채취

}

void solution(int y, int x, int cnt){
    if(cnt == 2) {
        ans = max(ans, maxProfit[0] + maxProfit[1]);
        return;
    }

    int j = x;
    for (int i = y; i < N; i++){ // 일꾼 1
        for (; j < N - M + 1; j++){
            maxProfit[cnt] = 0;
            get_max_profit(i, j, cnt, 0, 0, 0); // 해당 지점에서의 일꾼(cnt+1)의 최대 채취 양 구하기
            solution(i, j + M, cnt + 1);  // 일꾼 2
        } j = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for (int t = 1; t <= T; t++){
        ans = 0;
        input();
        solution(0, 0, 0);
        cout << "#" << t << " " << ans << "\n";
    }
}