SWEA 2115 - 벌꿀채취

Java

2115 번 - 벌꿀채취

문제

벌통들의 크기 N과 벌통에 있는 꿀의 양에 대한 정보, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 주어진다.

이때 두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대가 되는 경우를 찾고, 그 때의 최대 수익을 출력하는 프로그램을 작성하라.

접근 방법

처음 풀었을 때는, 조금 단순하게 접근하였다.
첫 번째 꿀벌의 위치 y, x / 두 번째 꿀벌의 위치 y, x를 지정해주는 4중 for문으로 각 위치를 정해준다.

두 꿀벌의 위치에서 각각 m개만큼 연속되게 꿀을 선택한다.
만약 선택한 꿀의 합이 c 이상이면, DFS를 사용하여 m개중 c를 넘지 않는 한 제일 많은 양의 꿀을 선택하게한다.

구한 꿀의 양 중 최대 값을 갱신하여 해결하였다.

코드

import java.io.*;
import java.util.*;

class Solution {
	static int result = 0, n, m, c;
	static double maxHoney;
	static int[][] beejar;
	static int[] honeySel;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		
    		beejar = new int[n][n];
    		honeySel = new int[m];
    		
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			for(int j = 0; j < n; j++) {
    				beejar[i][j] = stoi(stk.nextToken());
    			}
    		}
    		int firstHoney, honey= 0;
    		int firSum = 0, secSum = 0;
    		// 첫번째 일꾼 꿀 선택
    		for(int i1 = 0; i1 < n; i1++) {
    			for(int j1 = 0; j1 < n - m + 1; j1++) {
    				firstHoney = 0;
    				firSum = 0;
    				
    				// 첫 번째 꿀벌이 m개 만큼 꿀을 선택한다.
    				for(int k = j1; k < m + j1; k++) {
    					firSum += beejar[i1][k];
    					firstHoney += Math.pow(beejar[i1][k], 2);
    					honeySel[k - j1] = beejar[i1][k];
    				}
    				
    				// c보다 넘으면 c를 넘지 않는 한에서 꿀을 선택한다
    				if(firSum > c) {
    					maxHoney = 0;
    					DFS(0,0,0,0);
    					firstHoney = (int) maxHoney;
    				}
    				
    	    		// 두번째 일꾼 꿀 선택    				
    				for(int i2 = i1; i2 < n; i2++) {
    					// 첫번째 일꾼과 두번째 일꾼이 같은 라인에 있으면
    					if(i1 == i2) {
	    					for(int j2 = j1 + m; j2 < n - m + 1; j2++) {
	    						honey = firstHoney;
	    						
	    						// 두 번째 꿀벌이 m개 만큼 꿀을 선택한다.
	    						for(int k = j2; k < m + j2; k++) {
	    							secSum += beejar[i2][k];
	    							honey += Math.pow(beejar[i2][k], 2);
	    							honeySel[k - j2] = beejar[i2][k];
	    	    				}
	    						// 두 번째 꿀벌이 선택한 꿀의 양이 c를 넘으면 c를 넘지 않는 한에서 꿀을 선택한다
	    						if(secSum > c) {
	    	    					maxHoney = 0;
	    	    					DFS(0,0,0, firstHoney);
	    	    					honey = (int) maxHoney;
	    	    				}
	    						
	    						result = Math.max(result, honey);
	    						//System.out.println(i1 + " " + j1 + " " + i2 + " " + j2);
	    					}
    					}
    					// 첫번째 일꾼과 두번째 일꾼이 다른 라인에 있으면    					
    					else {
	    					for(int j2 = 0; j2 < n - m + 1; j2++) {
	    						honey = firstHoney;
	    						
	    						for(int k = j2; k < m + j2; k++) {
	    							secSum += beejar[i2][k];
	    							honey += Math.pow(beejar[i2][k], 2);
	    							honeySel[k - j2] = beejar[i2][k];
	    	    				}
	    						
	    						if(secSum > c) {
	    	    					maxHoney = 0;
	    	    					DFS(0,0,0, firstHoney);
	    	    					honey = (int) maxHoney;
	    	    				}
	    						
	    						result = Math.max(result, honey);
	    					}	
    					}
    				}
    			}
    		}
    		
    		System.out.println("#" + tidx + " " + result);
    	}
    	
	}
	// 선택한 m개의 꿀 중에서 c를 넘지 않는 한에서, 꿀들의 합이 제일 큰 것을 찾는다 
	static void DFS(int lv, int sum, int start, double powSum) {
		if(lv == m) {
			maxHoney = Math.max(powSum, maxHoney);
			return;
		}
		
		for(int i = start; i < m; i++) {
			
			if(sum + honeySel[i] <= c)
				DFS(lv + 1, sum + honeySel[i], i + 1, powSum + Math.pow(honeySel[i], 2));
			
			DFS(lv + 1, sum, i + 1, powSum);
		}
		
	}
	
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

1시간 정도 흘러가는 대로 짜다보니 맞은 문제.
for문으로 다루는건 실수를 하는 경우가 정말 많다.

개선할 점

4중 for문이 아닌, DFS를 사용하여 각 꿀벌의 위치를 정하도록 개선하자.